这题是模板题，先两个dfs把树剖开，重新编号，再借助线段树求解，求路径上的权值和还需要借助lca的思路先跳到同一条链上再利用区间求和。
#include <iostream>
#include <cstring>
#include <cstdio>
#define MIN -0x3f3f3f3f
#define mem(a,b) memset((a),(b),sizeof((a)))
using namespace std;
int mod=0x3f3f3f3f;
int n,m,r;
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f*x;
}
struct Edge{
int to;
int next;
int length;
};
Edge edge[400010];
int count[100010],head[100010],tot=0,heavy_son[100010];
void addedge(int u,int v){
edge[++tot].to=v;
edge[tot].length=1;
edge[tot].next=head[u];
head[u]=tot;
return ;
}
int dep[100010],father[100010],child_tree[100010];
int a[400010];
//第一次dfs 记录每个点重儿子编号，子节点数目，父节点编号
void dfs1(int u,int fa){
register int i;
father[u]=fa;
int maxson=-1;
for(i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v!=fa){
dep[v]=dep[u]+1;
dfs1(v,u);
if(child_tree[u]==0) child_tree[u]=1;
if(child_tree[v]==0) child_tree[v]=1;
child_tree[u]+=child_tree[v];
if(child_tree[v]>maxson){
maxson=child_tree[v];
heavy_son[u]=v;
}
}
}
return ;
}
int id[100010],cnt=0,top_line[100010];
//第二次dfs，节点重新编号，先处理重儿子，在处理轻儿子，轻儿子自己成一条链
void dfs2(int u,int top){
register int i;
id[u]=++cnt;
count[cnt]=a[u];
top_line[u]=top;
if(!heavy_son[u]) return;
dfs2(heavy_son[u],top);
for(i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v!=father[u]&&v!=heavy_son[u]) dfs2(v,v);
}
}
int maxn[100010];
//建线段树，跟普通线段上一模一样
void build(int root,int l,int r){
if(l==r){
maxn[root]=count[l];
a[root]=count[l];
a[root]%=mod;
return ;
}
build(root<<1,l,(l+r)>>1);
build(root<<1|1,((l+r)>>1)+1,r);
a[root]=(a[root<<1]+a[root<<1|1])%mod;
maxn[root]=max(maxn[root<<1],maxn[root<<1|1]);
}
int lazy[400010],len;
//下传lazy数组
void pushdown(int root,int len2){
lazy[root<<1]+=lazy[root];
lazy[root<<1|1]+=lazy[root];
a[root<<1]+=lazy[root]*(len2-(len2>>1));
a[root<<1|1]+=lazy[root]*(len2>>1);
a[root<<1]%=mod;
a[root<<1|1]%=mod;
lazy[root]=0;
}
//区间更新
void update(int root,int l,int r,int left,int right,int add){
if(left<=l&&r<=right){
lazy[root]+=add;
len=r-l+1;
a[root]+=add*len;
maxn[root]=a[root];//+add;
}
else{
len=r-l+1;
int mid=(l+r)>>1;
if(lazy[root]) pushdown(root,len);
if(left<=mid) update(root<<1,l,mid,left,right,add);
if(right>mid) update(root<<1|1,mid+1,r,left,right,add);
a[root]=(a[root<<1]+a[root<<1|1])%mod;
maxn[root]=max(maxn[root<<1],maxn[root<<1|1]);
}
return ;
}
//路径区间修改，lca的思想，x,y不在一条链上，先将深度更深的x跳到链首，同时区间修改。不在一条链上，继续往上跳
//跳到一条连上了，就用区间修改就可以了。
void update_road(int x,int y,int add){
add%=mod;
while(top_line[x]!=top_line[y]){
if(dep[top_line[x]]<dep[top_line[y]]) swap(x,y);
update(1,1,n,id[top_line[x]],id[x],add);
x=father[top_line[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y],add);
return ;
}
int res=MIN;
int res2=MIN;
//区间求和
void query(int root,int l,int r,int left,int right){
if(left<=l&&r<=right){res+=a[root];res2=max(res2,maxn[root]);res%=mod;return ;}
else{
len=(r-l)+1;
int mid=(l+r)>>1;
if(lazy[root]) pushdown(root,len);
if(left<=mid) query(root<<1,l,mid,left,right);
if(mid<right) query(root<<1|1,mid+1,r,left,right);
}
return ;
}
//路径区间求和，lca的思想，x,y不在一条链上，先将深度更深的x跳到链首，同时计算区间和。不在一条链上，继续往上跳
//跳到一条连上了，就用区间求和就可以了。
int road_sum(int x,int y){
int ans=0;
while(top_line[x]!=top_line[y]){
if(dep[top_line[x]]<dep[top_line[y]]) swap(x,y);
res=0;
query(1,1,n,id[top_line[x]],id[x]);
ans+=res;ans%=mod;
x=father[top_line[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=0;
query(1,1,n,id[x],id[y]);
ans+=res;
return ans%mod;
}
//修改子树，编号是连续的
void update_tree(int x,int add){
update(1,1,n,id[x],id[x]+child_tree[x]-1,add);
}
//子树求和，编号是连续的
int tree_sum(int x){
res=0;
query(1,1,n,id[x],id[x]+child_tree[x]-1);
return res;
}
//路径求极值
int road_max(int x,int y){
int ans=MIN;
while(top_line[x]!=top_line[y]){
if(dep[top_line[x]]<dep[top_line[y]]) swap(x,y);
res2=MIN;
query(1,1,n,id[top_line[x]],id[x]);
ans=max(ans,res2);
x=father[top_line[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res2=MIN;
query(1,1,n,id[x],id[y]);
ans=max(ans,res2);
return ans;
}
int main(){
mem(id,0);
mem(dep,0);
mem(head,-1);
register int i;
n=read();
for(i=1;i<n;i++){
int u,v;
u=read();v=read();
addedge(u,v);
addedge(v,u);
}
for(i=1;i<=n;i++){
a[i]=read();
}
dfs1(1,1);
dfs2(1,1);
mem(a,0);
build(1,1,n);
m=read();//m即q；
while(m--){
char s[10];
int u,t;
scanf("%s",s);
u=read();t=read();
if(s[3]=='N'){
update_road(u,u,t-count[id[u]]);
count[id[u]]=t;
}
else if(s[3]=='X'){
printf("%d\n",road_max(u,t));
}
else if(s[3]=='M'){
printf("%d\n",road_sum(u,t));
}
}
return 0;
}
有话要说...