Description
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。
我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身
Input & Output
Input
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来一行n个整数，第i个整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
Output
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
Sample
Input
41 22 34 14 2 1 312QMAX 3 4QMAX 3 3QMAX 3 2QMAX 2 3QSUM 3 4QSUM 2 1CHANGE 1 5QMAX 3 4CHANGE 3 6QMAX 3 4QMAX 2 4QSUM 3 4Output
412210656516Solution
资瓷单点修改，路径查询最大值，路径查询点权和，比较裸的树剖。怕不是常数比较大只过了洛谷（逃
Code：
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cctype>#include <string>using std::min;using std::max;using std::swap;using std::isdigit;using std::memset;using std::string;using std::cin;using std::cout;using std::endl;using std::ios;const int maxn = 30005;struct edge{ ???int to,nxt;}e[maxn<<1];struct node{ ???int w,mx,tag; ???node() ???{ ???????mx = w = tag = 0; ???}}tr[maxn << 2];int lnk[maxn],edgenum;int top[maxn],size[maxn],dep[maxn],son[maxn],f[maxn],dfn[maxn],dfn2[maxn];int cnt;int w[maxn],v[maxn],n,m,q;void add(int bgn,int end){ ???e[++edgenum].to = end; ???e[edgenum].nxt = lnk[bgn]; ???lnk[bgn] = edgenum;}void dfs(int x,int fa,int d){ ???size[x] = 1; ???f[x] = fa; ???dep[x] = d; ???for(int p = lnk[x]; p; p = e[p].nxt) ???{ ???????int y = e[p].to; ???????if(y == fa)continue; ???????dfs(y, x, d + 1); ???????size[x] += size[y]; ???????if(size[y] > size[son[x]]) son[x] = y; ???}}void dfs2(int x,int init){ ???dfn[x] = ++cnt; ???w[cnt] = v[x]; ???top[x] = init; ???if(!son[x])return; ???dfs2(son[x],init); ???for(int p = lnk[x]; p; p = e[p].nxt) ???{ ???????int y = e[p].to; ???????if(y == f[x]||y == son[x])continue; ???????dfs2(y,y); ???}}void build(int cur,int l,int r){ ???if(l == r) ???{ ???????tr[cur].w = w[l]; ???????tr[cur].mx = w[l]; ???????return; ???} ???int mid = (l + r) >> 1; ???build(cur<<1,l,mid); ???build(cur<<1|1,mid + 1,r); ???tr[cur].w = tr[cur<<1].w + tr[cur<<1|1].w; ???tr[cur].mx = max(tr[cur<<1].mx,tr[cur<<1|1].mx);}int querys(int cur,int l,int r,int L,int R){ ???int res = 0; ???if(L <= l && R >= r) ???{ ???????res += tr[cur].w; ???????return res; ???} ???int mid = (l+r)>>1; ???if(L<=mid) res += querys(cur<<1,l,mid,L,R); ???if(R>mid) res += querys(cur<<1|1,mid+1,r,L,R); ???return res;}int queryx(int cur,int l,int r,int L,int R){ ???int res = -214748; ???if(L <= l && R >= r) ???????return tr[cur].mx; ???int mid = (l+r)>>1; ???if(L<=mid) res = max(res, queryx(cur<<1,l,mid,L,R)); ???if(R>mid) res = max(res, queryx(cur<<1|1,mid+1,r,L,R)); ???return res;}void pupdate(int cur,int l,int r,int p,int c){ ???if(l == r) ???{ ???????tr[cur].w = c; ???????tr[cur].mx = c; ???????return; ???} ???else{ ???????int mid = (l+r)>>1; ???????if(p <= mid)pupdate(cur<<1,l,mid,p,c); ???????else pupdate(cur<<1|1,mid+1,r,p,c); ???????tr[cur].w = tr[cur<<1].w + tr[cur<<1|1].w; ???????tr[cur].mx = max(tr[cur<<1].mx,tr[cur<<1|1].mx); ???} ??}//---------------------------int queryts(int x,int y){ ???int ans = 0; ???while(top[x] != top[y]) ???{ ???????if(dep[top[x]] < dep[top[y]])swap(x,y); ???????ans += querys(1,1,n,dfn[top[x]],dfn[x]); ???????x = f[top[x]]; ???} ???if(dep[x]>dep[y])swap(x,y); ???ans += querys(1,1,n,dfn[x],dfn[y]); ???return ans;}int querytx(int x,int y){ ???int ans = -214748; ???while(top[x] != top[y]) ???{ ???????if(dep[top[x]] < dep[top[y]])swap(x,y); ???????ans = max(ans, queryx(1,1,n,dfn[top[x]],dfn[x])); ???????x = f[top[x]]; ???} ???if(dep[x] > dep[y])swap(x,y); ???ans = max(ans, queryx(1,1,n,dfn[x],dfn[y])); ???return ans;}int main(){ ???ios::sync_with_stdio(false); ???string s; ???int x,y; ???cin >> n; ???for(int i = 1; i < n; ++i) ???{ ???????cin >> x >> y; ???????add(x,y); ???????add(y,x); ???} ???for(int i = 1; i <= n; ++i) ???????cin >> v[i]; ???dfs(1,0,1); ???dfs2(1,1); ???build(1,1,n); ???cin >> q; ???for(int i = 1; i <= q; ++i) ???{ ???????cin >> s; ???????if(s[0] == 'C') ???????{ ???????????cin >> x >> y; ???????????pupdate(1,1,n,dfn[x],y); ???????} ???????else if(s[0] == 'Q' && s[1] == 'M') ???????{ ???????????cin >> x >> y; ???????????cout << querytx(x,y) << endl; ???????} ???????else ???????{ ???????????cin >> x >> y; ???????????cout << queryts(x,y) << endl; ???????} ???} ???return 0;}[JSOI2008][BZOJ1036] 树的统计 - 树链剖分
原文地址：https://www.cnblogs.com/nishikino-curtis/p/9047737.html