[ZJOI2008]树的统计https://www.luogu.org/problemnew/show/P2590
题目描述
一棵树上有(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)个整数(w_i)表示节点(i)的权值。
接下来(1)行，为一个整数(q)，表示操作的总数。
接下来(q)行，每行一个操作，以(CHANGE) (u) (t)或者(QMAX) (u) (v)或者(QSUM) (u) (v)的形式给出。
输出格式：
对于每个(QMAX)或者(QSUM)的操作，每行输出一个整数表示要求输出的结果。
输入样例：
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
输出样例：
4
1
2
2
10
6
5
6
5
16
说明
对于(100％)的数据，保证(1<=n<=30000，0<=q<=200000)；中途操作中保证每个节点的权值(w)在(-30000)到(30000)之间。
很简单的树链剖分模板题
单点修改,区间查询,线段树维护最大值(Max),点权和(sum)
1.无根树任选节点作根即可
2.查询(Max)的时候注意(Ans)初始化为-inf
#define RG register
#include<cstdio>
#include<iostream>
using namespace std;
const int N=31000;
inline int read()
{
RG int x=0,w=1;RG char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
int n,Q,cnt,ct;
int last[N],val[N],dep[N],dfn[N],top[N],size[N],rk[N],fa[N],son[N];
int sum[N<<2],Max[N<<2];
struct edge{int to,next;}e[N<<1];
inline void insert(int u,int v)
{
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void dfs1(int now)
{
size[now]=1;
for(int i=last[now];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa[now])continue;
fa[v]=now;
dep[v]=dep[now]+1;
dfs1(v);
size[now]+=size[v];
if(size[v]>size[son[now]])son[now]=v;
}
}
void dfs2(int now,int Top)
{
top[now]=Top;dfn[now]=++ct;rk[ct]=now;
if(son[now])dfs2(son[now],Top);
for(int i=last[now];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa[now]||v==son[now])continue;
dfs2(v,v);
}
}
inline void Pushup(int root)
{
sum[root]=sum[root<<1]+sum[root<<1|1];
Max[root]=max(Max[root<<1],Max[root<<1|1]);
}
void Build(int root,int l,int r)
{
if(l==r){sum[root]=Max[root]=val[rk[l]];return;}
int mid=(l+r)>>1;
Build(root<<1,l,mid);
Build(root<<1|1,mid+1,r);
Pushup(root);
}
void Modify(int root,int l,int r,int s,int k)
{
if(l==s&&r==s){sum[root]=Max[root]=k;return;}
int mid=(l+r)>>1;
if(mid>=s)Modify(root<<1,l,mid,s,k);
else Modify(root<<1|1,mid+1,r,s,k);
Pushup(root);
}
int Query(int root,int l,int r,int ll,int rr,int op)
{
if(ll<=l&&r<=rr)
{
if(op)return sum[root];
return Max[root];
}
int mid=(l+r)>>1,Ans=0;
if(!op)Ans=-1e9;
if(ll<=mid)
{
if(op)Ans+=Query(root<<1,l,mid,ll,rr,op);
else Ans=max(Ans,Query(root<<1,l,mid,ll,rr,op));
}
if(mid<rr)
{
if(op)Ans+=Query(root<<1|1,mid+1,r,ll,rr,op);
else Ans=max(Ans,Query(root<<1|1,mid+1,r,ll,rr,op));
}
return Ans;
}
inline int Query_Tree(int x,int y,int op)
{
int Ans=0;
if(!op)Ans=-1e9;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
if(op)Ans+=Query(1,1,n,dfn[top[x]],dfn[x],op);
else Ans=max(Ans,Query(1,1,n,dfn[top[x]],dfn[x],op));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(op)Ans+=Query(1,1,n,dfn[x],dfn[y],op);
else Ans=max(Ans,Query(1,1,n,dfn[x],dfn[y],op));
return Ans;
}
int main()
{
n=read();
for(int i=1;i<n;i++)
{
int a=read(),b=read();
insert(a,b);
}
for(int i=1;i<=n;i++)val[i]=read();
dep[1]=1;
dfs1(1);
dfs2(1,1);
Build(1,1,n);
Q=read();
RG char act[10];
RG int u,v;
while(Q--)
{
scanf("%s",act);
u=read();v=read();
if(act[3]=='X')printf("%d
",Query_Tree(u,v,0));//查询最大值
if(act[3]=='M')printf("%d
",Query_Tree(u,v,1));//查询点权和
if(act[3]=='N')Modify(1,1,n,dfn[u],v);
}
return 0;
}