灵异影像

代码：

#include<bits/stdc++.h>
#define ll long long
#define N (int)1e5+5
using namespace std;
int n,m,root=1,mod,cnt,tot,b[N][2],a[N],head[N],dep[N],sz[N],son[N],id[N],top[N],fat[N],la1[N];
ll na[N],tr[N<<2],la[N<<2];
struct Edge{
	int u,v,w,nxt;
}e[N<<1];
inline void add(int u,int v,int w){
	e[++cnt]=Edge{u,v,w,head[u]};
	head[u]=cnt;
}
inline void dfs1(int u,int fa){
	dep[u]=dep[fa]+1;sz[u]=1;fat[u]=fa;
	for(int i=head[u];i;i=e[i].nxt){
		if(e[i].v==fa) continue;
		a[e[i].v]=e[i].w;
		dfs1(e[i].v,u);
		sz[u]+=sz[e[i].v];
		if(sz[e[i].v]>sz[son[u]]) son[u]=e[i].v;
	}
}
inline void dfs2(int u,int fa){
	id[u]=++tot,na[tot]=a[u];
	if(son[u]) top[son[u]]=top[u],dfs2(son[u],u);
	for(int i=head[u];i;i=e[i].nxt){
		if(e[i].v==fa||e[i].v==son[u]) continue;
		top[e[i].v]=e[i].v;
		dfs2(e[i].v,u);
	}
}
inline void pushup(int p){
	tr[p]=max(tr[p<<1],tr[p<<1|1]);
}
inline void build(int l,int r,int p){
	la1[p]=-1;
	if(l==r){
		tr[p]=na[l];
		return ;
	}
	int m=(l+r)>>1;
	build(l,m,p<<1);build(m+1,r,p<<1|1);
	pushup(p);
}
inline void pushdown(int s,int t,int p){
	int m=s+t>>1;
	if(la1[p]!=-1) tr[p<<1]=la1[p],tr[p<<1|1]=la1[p],la1[p<<1]=la1[p],la1[p<<1|1]=la1[p];
	if(la[p]) tr[p<<1]+=la[p],tr[p<<1|1]+=la[p],la[p<<1]+=la[p],la[p<<1|1]+=la[p];
	la[p]=0;
	la1[p]=-1;
}
inline void update(int l,int r,int s,int t,int c,int p){
	if(l<=s&&t<=r){
		tr[p]+=c;
		la[p]+=c;
		return ;
	}
	pushdown(s,t,p);
	int m=(s+t)>>1;
	if(l<=m) update(l,r,s,m,c,p<<1);
	if(r>m) update(l,r,m+1,t,c,p<<1|1);
	pushup(p);
}
inline void update1(int l,int r,int s,int t,int c,int p){
	if(l<=s&&t<=r){
		tr[p]=c;
		la1[p]=c;
		return ;
	}
	pushdown(s,t,p);
	int m=(s+t)>>1;
	if(l<=m) update1(l,r,s,m,c,p<<1);
	if(r>m) update1(l,r,m+1,t,c,p<<1|1);
	pushup(p);
}
inline ll query(int l,int r,int s,int t,int p){
	if(l<=s&&t<=r) return tr[p];
	pushdown(s,t,p);
	ll m=(s+t)>>1,v=0;
	if(l<=m) v=query(l,r,s,m,p<<1);
	if(r>m) v=max(query(l,r,m+1,t,p<<1|1),v);
	return v;
}
void update_path(int u,int v,int c){
	while(top[u]^top[v]){
		if(dep[top[u]]<dep[top[v]]) u^=v^=u^=v;
		update(id[top[u]],id[u],1,n,c,1);
		u=fat[top[u]];
	}
	if(dep[u]<dep[v]) u^=v^=u^=v;
	v=son[v];
	update(id[v],id[u],1,n,c,1);
}
void update_path1(int u,int v,int c){
	while(top[u]^top[v]){
		if(dep[top[u]]<dep[top[v]]) u^=v^=u^=v;
		update1(id[top[u]],id[u],1,n,c,1);
		u=fat[top[u]];
	}
	if(dep[u]<dep[v]) u^=v^=u^=v;
	v=son[v];
	update1(id[v],id[u],1,n,c,1);
}
ll query_path(int u,int v){
	ll ans=0;
	while(top[u]^top[v]){
		if(dep[top[u]]<dep[top[v]]) u^=v^=u^=v;
		ans=max(query(id[top[u]],id[u],1,n,1),ans);
		u=fat[top[u]];
	}
	if(dep[u]<dep[v]) u^=v^=u^=v;
	v=son[v];
	return max(query(id[v],id[u],1,n,1),ans);
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v,w;i<n;++i) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w),b[i][0]=u,b[i][1]=v;
	top[root]=root;
	dfs1(root,0);
	dfs2(root,0);
	son[0]=na[1];
	build(1,n,1);
	for(;;){
		char s[8];
		int u,v,w;
		scanf("\n%s",s);
		if(s[0]=='S') break;
		scanf(" %d %d",&u,&v);
		if(s[0]=='C'&&s[1]=='h'){
			update_path1(b[u][0],b[u][1],v);
		}
		else if(s[0]=='C'){
			scanf(" %d",&w),update_path1(u,v,w);
		}
		else if(s[0]=='A') scanf(" %d",&w),update_path(u,v,w);
		else printf("%lld\n",query_path(u,v));
	}
	return 0;
}

能过样例