【题解】「ZJOI2008」树的统计（树链剖分）

本文主要是介绍【题解】「ZJOI2008」树的统计（树链剖分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

【题目描述】
一棵树上有 $n$ 个节点，编号分别为 $1$ 到 $n$ ，每个节点都有一个权值 $w$ 。我们将以下面的形式来要求你对这棵树完成一些操作：
$I .$ $C H A N G E$ $u$ $t$ : 把结点 $u$ 的权值改为 $t$
$I I .$ $Q M A X$ $u$ $v$ : 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值
$I I I .$ $Q S U M$ $u$ $v$ : 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和，注意：从点 $u$ 到点 $v$ 的路径上的节点包括 $u$ 和 $v$ 本身
【输入】
输入的第一行为一个整数 $n$ ，表示节点的个数。
接下来 $n - 1$ 行，每行 $2$ 个整数 $a$ 和 $b$ ，表示节点 $a$ 和节点 $b$ 之间有一条边相连。
接下来 $n$ 行，每行一个整数，第 $i$ 行的整数 $w_i$ 表示节点 $i$ 的权值。
接下来 $1$ 行，为一个整数 $q$ ，表示操作的总数。
接下来 $q$ 行，每行一个操作，以“ $C H A N G E$ $u$ $t$ ”或者“ $Q M A X$ $u$ $v$ ”或者“ $Q S U M$ $u$ $v$ ”的形式给出。
对于 $100 ％$ 的数据，保证 $1 < = n < = 30000$ ， $0 < = q < = 200000$ ；中途操作中保证每个节点的权值 $w$ 在 $- 30000$ 到 $30000$ 之间。
【输出】
对于每个“ $Q M A X$ ”或者“ $Q S U M$ ”的操作，每行输出一个整数表示要求输出的结果。
【样例输入】

4
1 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

【样例输出】

算法分析

树链剖分模板题。

参考程序

#include<bits/stdc++.h>
#define N 200100 
using namespace std;
int head[N],nxt[N],to[N],w[N],tot;
int n,m;
int father[N],deep[N],size[N];//父节点，深度，子树结点数 
int son[N],top[N];//重儿子，所在重路径的顶部结点(深度最小的结点)
int id[N],rev[N],t;//在线段树中的下标(dfs序)，线段树中下标的结点,即rev[id[u]]=u ,dfs序号 
int sum[2*N],Max[2*N]; //线段树 
int ans_sum,ans_max;
void Add(int u,int v)
{nxt[++tot]=head[u];to[tot]=v;head[u]=tot;
}
void dfs1(int u,int dad)
{size[u]=1;  //本身结点数为1 father[u]=dad;   deep[u]=deep[dad]+1;for(int i=head[u];i!=-1;i=nxt[i]){int v=to[i];if(v!=dad){dfs1(v,u);size[u]+=size[v];if(size[v]>size[son[u]]) son[u]=v;//找重儿子 }}
}
void dfs2(int u,int dad)
{int v=son[u];if(v)  						//优先选择重儿子 {id[v]=++t;				//dfs序列 top[v]=top[u];rev[t]=v;dfs2(v,u); }for(int i=head[u];i!=-1;i=nxt[i]){v=to[i];if(!top[v]){id[v]=++t;top[v]=v;        rev[t]=v;dfs2(v,u);}}
}
void built(int k,int l,int r)   //线段树建树
{if(l==r)    {Max[k]=sum[k]=w[rev[l]];return;} 	//初始化 int mid=(l+r)/2;built(2*k,l,mid);built(2*k+1,mid+1,r);sum[k]=sum[2*k]+sum[2*k+1];Max[k]=max(Max[2*k],Max[2*k+1]);
} 
void change(int k,int l,int r,int x,int v)  //单点修改 
{if(l>r) return;if(l==r&&x==l)  {sum[k]=Max[k]=v;return;}int mid=(l+r)/2;if(x>=l&&x<=mid) change(2*k,l,mid,x,v);if(x>=mid+1&&x<=r) change(2*k+1,mid+1,r,x,v);sum[k]=sum[2*k]+sum[2*k+1];Max[k]=max(Max[2*k],Max[2*k+1]);
}
void query(int k,int l,int r,int x,int y)
{if(x>r||y<l) return ;if(x<=l&&r<=y) {ans_sum+=sum[k];ans_max=max(ans_max,Max[k]);return;}int mid=(l+r)/2;if(x<=mid) query(2*k,l,mid,x,y);if(y>=mid+1) query(2*k+1,mid+1,r,x,y);
} 
void ask(int u,int v)
{       int fu=top[u],fv=top[v];while(fu!=fv)   //不在同一条重链上 {if(deep[fu]<deep[fv]) {swap(u,v);swap(fu,fv);}   //选择深度大的往上跳query(1,1,n,id[fu],id[u]);  //访问路径 fu->u u=father[fu];fu=top[u]; }if(deep[u]>deep[v]) swap(u,v);   //已经跳到同一条重路径上了 query(1,1,n,id[u],id[v]);
}
int main()
{memset(head,-1,sizeof(head));scanf("%d",&n);int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);Add(x,y);Add(y,x);}for(int i=1;i<=n;i++)scanf("%d",&w[i]);scanf("%d",&m);dfs1(1,0);id[1]=++t;  //初始化根节点 top[1]=1;rev[1]=1;dfs2(1,0); built(1,1,n); char s[10];for(int i=1;i<=m;i++){scanf("%s%d%d",s,&x,&y);  if(s[0]=='C')   change(1,1,n,id[x],y);else{ans_sum=0;ans_max=0x80000000;		//int最小值 ask(x,y); 				//路径询问 if(s[0]=='Q'&&s[1]=='M')    printf("%d\n",ans_max);if(s[0]=='Q'&&s[1]=='S')    printf("%d\n",ans_sum);}}return 0;
}