bzoj 1036 [ZJOI2008]樹的統(tǒng)計Count（樹鏈剖分入門系列）
??? 其實(shí)很早就看過樹鏈剖分了，當(dāng)時看得云里霧里，主要還是局限于概念，實(shí)際運(yùn)用和概念理解之間還是有很大的隔閡。這隔閡只能通過做題來理解。
基本概念：starszys
加強(qiáng)理解：大神養(yǎng)成中
簡單運(yùn)用：hzwer
系列題目：kuangbin
博客系列：hzwer
【樹鏈剖分第1題】
??? 完全是按照hzwer的這篇博客依葫蘆畫瓢寫的，雖然只是按著寫，但感覺對于這種比較抽象的算法，還是按著寫入門比較好，在寫的過程中，會逐步理解，不會摸不著頭腦，單純看10多篇博客，不如寫1道題來的實(shí)在。在寫的過程中，還了解了倍增算法，算是小收獲吧，對大神可能就什么都不是了。
題目鏈接：bzoj 1036
題面：
Submit: 10439??Solved: 4228
[Submit][Status][Discuss]
一棵樹上有n個節(jié)點(diǎn)，編號分別為1到n，每個節(jié)點(diǎn)都有一個權(quán)值w。我們將以下面的形式來要求你對這棵樹完成一些操作： I. CHANGE u t : 把結(jié)點(diǎn)u的權(quán)值改為t II. QMAX u v: 詢問從點(diǎn)u到點(diǎn)v的路徑上的節(jié)點(diǎn)的最大權(quán)值 III. QSUM u v: 詢問從點(diǎn)u到點(diǎn)v的路徑上的節(jié)點(diǎn)的權(quán)值和 注意：從點(diǎn)u到點(diǎn)v的路徑上的節(jié)點(diǎn)包括u和v本身
Input輸入的第一行為一個整數(shù)n，表示節(jié)點(diǎn)的個數(shù)。接下來n – 1行，每行2個整數(shù)a和b，表示節(jié)點(diǎn)a和節(jié)點(diǎn)b之間有一條邊相連。接下來n行，每行一個整數(shù)，第i行的整數(shù)wi表示節(jié)點(diǎn)i的權(quán)值。接下來1行，為一個整數(shù)q，表示操作的總數(shù)。接下來q行，每行一個操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式給出。 對于100％的數(shù)據(jù)，保證1<=n<=30000，0<=q<=200000；中途操作中保證每個節(jié)點(diǎn)的權(quán)值w在-30000到30000之間。
Output對于每個“QMAX”或者“QSUM”的操作，每行輸出一個整數(shù)表示要求輸出的結(jié)果。
Sample Input 41 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4 Sample Output 4
1
2
2
10
6
5
6
5
16 HINT Source
樹的分治
代碼：
#include
#include
#include
#define N 30005
#define M 60010
#define inf 1e9
using namespace std;
struct edge
{
int to,next;
}E[M];
struct segTree
{
int l,r,maxn,sum;
}Tree[N*4];
bool vis[N];
//head數(shù)組存邊的信息，size存子樹上節(jié)點(diǎn)個數(shù)，deep存離根節(jié)點(diǎn)深度
//fa[i][j]表示的是i這個節(jié)點(diǎn)往上(2^j)的父親是誰
//val代表單點(diǎn)數(shù)值,cnt為邊分配的下標(biāo)，pos數(shù)組映射樹上點(diǎn)在線段數(shù)上的位置
//belong數(shù)組反映的是點(diǎn)在哪條重鏈上，其值取的是該重鏈頂點(diǎn)的標(biāo)號
int head[N],size[N],deep[N],fa[N][15];
int val[30010],cnt=0,sz=0,pos[30010],belong[30010];
int max(int a,int b)
{
return a>b?a:b;
}
//初始化，head值為0代表無后續(xù)邊
void init()
{
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
}
//添加雙向邊
void add_edge(int u,int v)
{
E[++cnt].to=v;E[cnt].next=head[u];head[u]=cnt;
E[++cnt].to=u;E[cnt].next=head[v];head[v]=cnt;
}
//計算size，fa，deep數(shù)組
void dfs1(int x)
{
//該點(diǎn)個數(shù)為1
size[x]=1;
//標(biāo)記訪問
vis[x]=1;
for(int i=1;i<=14;i++)
{
if(deep[x]<(1<deep[x]&&size[E[i].to]>size[k])
k=E[i].to;//找到重兒子
//不存在兒子，為葉子節(jié)點(diǎn)
if(k==0)return;
//其他兒子重新開辟新鏈
dfs2(k,chain);
for(int i=head[x];i;i=E[i].next)
if(deep[E[i].to]>deep[x]&&k!=E[i].to)
dfs2(E[i].to,E[i].to);//開辟新鏈
}
//求兩節(jié)點(diǎn)最近公共祖先
int lca(int x,int y)
{
if(deep[x]=0;i--)
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
if(x==y)return x;
else return fa[x][0];
}
//線段樹建樹
void build(int i,int l,int r)
{
Tree[i].l=l;
Tree[i].r=r;
if(l==r)
return;
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
//更新操作
void modify(int i,int p,int v)
{
int l=Tree[i].l,r=Tree[i].r;
int mid=(l+r)>>1;
if(l==r)
{
Tree[i].sum=Tree[i].maxn=v;
return;
}
if(p<=mid)
modify(i<<1,p,v);
else
modify(i<<1|1,p,v);
Tree[i].sum=Tree[i<<1].sum+Tree[i<<1|1].sum;
Tree[i].maxn=max(Tree[i<<1].maxn,Tree[i<<1|1].maxn);
}
//求最區(qū)間和
int qurysum(int i,int l,int r)
{
if(Tree[i].l==l&&Tree[i].r==r)
return Tree[i].sum;
int mid=(Tree[i].l+Tree[i].r)>>1;
if(r<=mid)return qurysum(i<<1,l,r);
else if(l>mid)return qurysum(i<<1|1,l,r);
else return qurysum(i<<1,l,mid)+qurysum(i<<1|1,mid+1,r);
}
//求區(qū)間最大
int qurymax(int i,int l,int r)
{
if(Tree[i].l==l&&Tree[i].r==r)
return Tree[i].maxn;
int mid=(Tree[i].l+Tree[i].r)>>1;
if(r<=mid)return qurymax(i<<1,l,r);
else if(l>mid) return qurymax(i<<1|1,l,r);
else return max(qurymax(i<<1,l,mid),qurymax(i<<1|1,mid+1,r));
}
//獲取x和他父親節(jié)點(diǎn)f之間的和
int get_sum(int x,int f)
{
int sum=0;
//不在1條鏈上
while(belong[x]!=belong[f])
{
//將x節(jié)點(diǎn)上移，并加上該重鏈上，x到其頂點(diǎn)的值
sum+=qurysum(1,pos[belong[x]],pos[x]);
x=fa[belong[x]][0];
}
//已經(jīng)移到同一條重鏈上，加上最后倆點(diǎn)間的和
sum+=qurysum(1,pos[f],pos[x]);
return sum;
}
//同求和
int get_max(int x,int f)
{
int maxn=-30010;
while(belong[x]!=belong[f])
{
maxn=max(maxn,qurymax(1,pos[belong[x]],pos[x]));
x=fa[belong[x]][0];
}
maxn=max(maxn,qurymax(1,pos[f],pos[x]));
return maxn;
}
int main()
{
char s[10];
int n,x,y,q,ans;
scanf("%d",&n);
init();
for(int i=1;i 
下載文檔
