https://www.luogu.org/problem/show?pid=2590#sub
题目描述
一棵树上有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本身
输入输出格式
输入格式：
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来一行n个整数，第i个整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
输出格式：
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
输入输出样例
输入样例#1：
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
输出样例#1：
4
1
2
2
10
6
5
6
5
16
说明
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
树剖模板
#include <algorithm>
#include <string>
#include <cstdio> using namespace std; const int N(+);
int n,u,v,val[N],q;
char op[]; int head[N],sumedge;
struct Edge
{
int u,v,next;
Edge(int u=,int v=,int next=):
u(u),v(v),next(next){}
}edge[N<<];
void ins(int u,int v)
{
edge[++sumedge]=Edge(u,v,head[u]);
head[u]=sumedge;
} int cnt,id[N],dfn[N],size[N],son[N],top[N],dad[N],deep[N];
void DFS(int u,int father,int deepth)
{
deep[u]=deepth;
dad[u]=father;
size[u]=;
son[u]=;
for(int i=head[u];i;i=edge[i].next)
{
int to=edge[i].v;
if(dad[u]==to) continue;
DFS(to,u,deepth+); size[u]+=size[to];
if(!son[u]||size[son[u]]<size[to]) son[u]=to;
}
}
void DFS_(int u,int Top)
{
top[u]=Top;
id[u]=++cnt;
dfn[cnt]=u;
if(son[u]) DFS_(son[u],Top);
for(int i=head[u];i;i=edge[i].next)
{
int to=edge[i].v;
if(to!=dad[u]&&to!=son[u]) DFS_(to,to);
}
} struct Tree
{
int l,r,mid,sumval,maxval;
}tree[N<<];
void Tree_up(int now)
{
tree[now].sumval=tree[now<<].sumval+tree[now<<|].sumval;
tree[now].maxval=max(tree[now<<].maxval,tree[now<<|].maxval);
}
void Tree_build(int now,int l,int r)
{
tree[now].l=l;tree[now].r=r;
if(l==r)
{
tree[now].maxval=val[dfn[l]];
tree[now].sumval=val[dfn[l]];
return ;
}
tree[now].mid=l+r>>;
Tree_build(now<<,l,tree[now].mid);
Tree_build(now<<|,tree[now].mid+,r);
Tree_up(now);
}
void Tree_change(int now,int to,int x)
{
if(tree[now].l==tree[now].r)
{
tree[now].maxval=x;
tree[now].sumval=x;
return ;
}
if(tree[now].mid>=to) Tree_change(now<<,to,x);
else if(tree[now].mid<to) Tree_change(now<<|,to,x);
Tree_up(now);
}
int Tree_querymax(int now,int l,int r)
{
if(tree[now].l==l&&tree[now].r==r) return tree[now].maxval;
if(tree[now].mid>=r) return Tree_querymax(now<<,l,r);
else if(tree[now].mid<l) return Tree_querymax(now<<|,l,r);
else return max(Tree_querymax(now<<,l,tree[now].mid),Tree_querymax(now<<|,tree[now].mid+,r));
}
int Tree_querysum(int now,int l,int r)
{
if(tree[now].l==l&&tree[now].r==r) return tree[now].sumval;
if(tree[now].mid>=r) return Tree_querysum(now<<,l,r);
else if(tree[now].mid<l) return Tree_querysum(now<<|,l,r);
else return Tree_querysum(now<<,l,tree[now].mid)+Tree_querysum(now<<|,tree[now].mid+,r);
} int List_querymax(int x,int y)
{
int ret=-1e9;
for(;top[x]!=top[y];x=dad[top[x]])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ret=max(ret,Tree_querymax(,id[top[x]],id[x]));
}
if(id[x]>id[y]) swap(x,y);
ret=max(ret,Tree_querymax(,id[x],id[y]));
return ret;
}
int List_querysum(int x,int y)
{
int ret=;
for(;top[x]!=top[y];x=dad[top[x]])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ret+=Tree_querysum(,id[top[x]],id[x]);
}
if(id[x]>id[y]) swap(x,y);
ret+=Tree_querysum(,id[x],id[y]);
return ret;
} int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d%d",&u,&v),ins(u,v),ins(v,u);
for(int i=;i<=n;i++) scanf("%d",val+i);
DFS(,,);DFS_(,);
Tree_build(,,n);
scanf("%d",&q);
for(;q--;)
{
scanf("%s%d%d",op,&u,&v);
if(op[]=='C') Tree_change(,id[u],v);
else if(op[]=='M') printf("%d\n",List_querymax(u,v));
else printf("%d\n",List_querysum(u,v));
}
return ;
}