提交记录

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+6;
struct Node {
	int to,next,data;
} edge[maxn];
struct Edge {
	int u,v,w;
} e[maxn];
struct Segment_tree {
	int l,r,dat,add,cov;
} T[maxn<<2];
int n,tot,cnt;
int Head[maxn],dep[maxn],siz[maxn],fa[maxn],son[maxn],top[maxn],id[maxn],rk[maxn],d[maxn];
char str[50];
void add(int x,int y,int v) {
	edge[tot]=Node {y,Head[x],v},Head[x]=tot++;
}
void spread(int p) {
	if (T[p].cov!=-1) {
		T[p << 1].dat = T[p << 1 | 1].dat = T[p].cov + T[p].add;
		T[p << 1].add = T[p << 1 | 1].add = T[p].add, T[p << 1].cov = T[p << 1 | 1].cov = T[p].cov;
	}

	else {
		T[p << 1].dat += T[p].add, T[p << 1 | 1].dat += T[p].add;
		T[p << 1].add += T[p].add, T[p << 1 | 1].add += T[p].add;
	}

	T[p].add =0, T[p].cov =-1;
}
void Build(int p,int l,int r) {
	T[p].l=l,T[p].r=r,T[p].cov=-1;
	if(l==r) {
		T[p].dat=d[rk[l]];
		return ;
	}
	int mid=l+r>>1;
	Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
	T[p].dat=max(T[p<<1].dat,T[p<<1|1].dat);
}
void change(int p,int l,int r,int v,bool t) {
	if(l<=T[p].l&&T[p].r<=r) {
		if(!t)T[p].dat=v,T[p].cov=v,T[p].add=0;
		else T[p].dat+=v,T[p].add+=v;
		return ;
	}
	int mid=T[p].l+T[p].r>>1;
	spread(p);
	if(l<=mid)
		change(p<<1,l,r,v,t);
	if(r>mid)
		change(p<<1|1,l,r,v,t);
	T[p].dat=max(T[p<<1].dat,T[p<<1|1].dat);
}
int ask(int p,int l,int r) {
	if(l<=T[p].l&&T[p].r<=r)
		return T[p].dat;
	spread(p);
	int mid=T[p].l+T[p].r>>1,res=0;
	if(l<=mid)
		res=max(res,ask(p<<1,l,r));
	if(r>mid)
		res=max(res,ask(p<<1|1,l,r));
	return res;
}
void dfs1(int x,int f,int depth) {
	fa[x]=f,dep[x]=depth,siz[x]=1;
	for(int i=Head[x]; ~i; i=edge[i].next)
		if(edge[i].to!=f) {
			dfs1(edge[i].to,x,depth+1),siz[x]+=siz[edge[i].to];
			d[edge[i].to]=edge[i].data;
			if(siz[edge[i].to]>siz[son[x]])
				son[x]=edge[i].to;
		}
}
void dfs2(int x,int t) {
	top[x]=t,id[x]=++cnt,rk[cnt]=x;
	if(!son[x])return ;
	dfs2(son[x],t);
	for(int i=Head[x]; ~i; i=edge[i].next)
		if(edge[i].to!=son[x]&&edge[i].to!=fa[x])
			dfs2(edge[i].to,edge[i].to);
}
void Update(int x,int y,int v,bool t) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		change(1,id[top[x]],id[x],v,t),x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	change(1,id[x]+1,id[y],v,t);
}
int Query(int x,int y) {
	int res=0;
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res=max(res,ask(1,id[top[x]],id[x])),x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return max(res,ask(1,id[x]+1,id[y]));
}
int main() {
	memset(Head,-1,sizeof Head);
	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),e[i]=Edge {u,v,w};
	dfs1(1,0,1),dfs2(1,1),Build(1,1,n);
	int x,y,v;
	while(~scanf("%s",str)&&str[0]!='S') {
		scanf("%d%d",&x,&y);
		if(str[0]=='A')
			scanf("%d",&v),Update(x,y,v,1);
		if(str[1]=='o')
			scanf("%d",&v),Update(x,y,v,0);
		if(str[1]=='h')
			change(1,id[e[x].u],id[e[x].v],y,0);
		if(str[0]=='M')
			printf("%d\n",Query(x,y));
	}
	return 0;
}