rt,3-71行是线段树，72-151行是树剖。

#include<bits/stdc++.h>
using namespace std;
#define Puck 1000005
#define puck -2e9
int n,a[Puck],tree[Puck<<2],tag[Puck<<2],tag2[Puck<<2];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
void add_up(int p){tree[p]=max(tree[ls(p)],tree[rs(p)]);}						//上传区间值 
void build(int p,int pl,int pr)												//p代表区间[pl,pr] 
	{
	tag[p]=0;tag2[p]=puck;if(pl==pr){tree[p]=a[pl];return;}								//叶子节点赋值
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid);build(rs(p),mid+1,pr); 
	add_up(p);
	}
void add_tag(int p,int pl,int pr,int d)										//懒一下 
	{
	if(tag2[p]!=puck)tag2[p]+=d;
	else tag[p]+=d;
	tree[p]+=d;
	} 
void gai_tag(int p,int pl,int pr,int d)
	{
	tag[p]=0;tag2[p]=tree[p]=d;
	}
void add_down(int p,int pl,int pr)											//懒重叠处理 
	{
	if(tag2[p]!=puck)
		{
		int mid=(pl+pr)>>1;
		gai_tag(ls(p),pl,mid,tag2[p]);gai_tag(rs(p),mid+1,pr,tag2[p]);
		tag2[p]=puck;
		}
	else if(tag[p])
		{
		int mid=(pl+pr)>>1;
		add_tag(ls(p),pl,mid,tag[p]);										//下传处理 
		add_tag(rs(p),mid+1,pr,tag[p]);
		tag[p]=0;
		}
	}
void add(int l,int r,int p,int pl,int pr,int d)								//修改 
	{
	if(l>r)return;
	if(l<=pl&&pr<=r){add_tag(p,pl,pr,d);return;}							//正好不用处理重叠 
	add_down(p,pl,pr);														//重叠处理 
	int mid=(pl+pr)>>1;
	if(l<=mid)add(l,r,ls(p),pl,mid,d);										 
	if(r>mid)add(l,r,rs(p),mid+1,pr,d);
	add_up(p);
	}
void gai(int l,int r,int p,int pl,int pr,int d)
	{
	if(l>r)return;
	if(l<=pl&&pr<=r){gai_tag(p,pl,pr,d);return;}
	add_down(p,pl,pr);
	int mid=(pl+pr)>>1;
	if(l<=mid)gai(l,r,ls(p),pl,mid,d);
	if(r>mid)gai(l,r,rs(p),mid+1,pr,d);
	add_up(p);
	}
int query(int l,int r,int p,int pl,int pr)
	{
	if(l>r)return -114514;
	if(l<=pl&&pr<=r)return tree[p];
	add_down(p,pl,pr);
	int ans=-1e9,mid=(pl+pr)>>1;
	if(l<=mid)ans=max(ans,query(l,r,ls(p),pl,mid));
	if(r>mid)ans=max(ans,query(l,r,rs(p),mid+1,pr));
	return ans;
	}
int fa[Puck],dep[Puck],siz[Puck],son[Puck],top[Puck],dfn[Puck],pos[Puck],cnt=0;
vector<int>e[Puck];
vector<pair<int,int> >e2[Puck];
void dfs0(int u,int f)
	{
	for(int i=0;i<e2[u].size();i++)
		{
		pair<int,int> v=e2[u][i];
		int x=v.first,d=v.second;
		if(x==f)continue;
		a[x]=d;dfs0(x,u);
		}
	}
void dfs1(int u,int f)
	{
	fa[u]=f;siz[u]=1;son[u]=0;dep[u]=dep[f]+1;
	for(int i=0;i<e[u].size();i++)
		{
		int v=e[u][i];
		if(v==f)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
		}
	}
void dfs2(int u,int tp)
	{
	top[u]=tp;dfn[u]=++cnt;pos[cnt]=u;
	if(son[u])dfs2(son[u],tp);
	for(int i=0;i<e[u].size();i++)
		{
		int v=e[u][i];
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
		}
	}
void upd1(int x,int y,int d)
	{
	while(top[x]!=top[y])
		{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		int dd=top[x];
		int xx=dfn[dd],yy=dfn[x];
		gai(xx,yy,1,1,n,d);
		x=fa[top[x]];
		}
	if(x==y)return;
	if(dep[x]>dep[y])swap(x,y);
	gai(dfn[son[x]],dfn[y],1,1,n,d);
	}
void upd2(int x,int y,int d)
	{
	while(top[x]!=top[y])
		{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		int dd=top[x];
		int xx=dfn[dd],yy=dfn[x];
		add(xx,yy,1,1,n,d);
		x=fa[top[x]];
		}
	if(x==y)return;
	if(dep[x]>dep[y])swap(x,y);
	add(dfn[son[x]],dfn[y],1,1,n,d);
	}
int query1(int x,int y)
	{
	int ans=-114514;
	while(top[x]!=top[y])
		{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		int dd=top[x];
		int xx=dfn[dd],yy=dfn[x];
		ans=max(ans,query(xx,yy,1,1,n));
		x=fa[top[x]];
		}
	if(x==y)return ans;
	if(dep[x]>dep[y])swap(x,y);
	ans=max(ans,query(dfn[son[x]],dfn[y],1,1,n));
	return ans;
	}
int q[Puck][2];
signed main()
	{
	//freopen("P4315_1.in","r",stdin);
	//freopen("P4315.out","w",stdout);
	cin>>n;
	for(int i=1;i<n;i++)
		{
		int x,y,d;cin>>x>>y>>d;
		e[x].push_back(y);e2[x].push_back({y,d});
		e[y].push_back(x);e2[y].push_back({x,d});
		q[i][0]=x;q[i][1]=y;
		}
	dfs0(1,1);
	build(1,1,n);
	dfs1(1,1);
	dfs2(1,1);
	while(1)
		{
		string s;cin>>s;
		if(s=="Stop")return 0;
		if(s=="Cover"){int x,y,d;cin>>x>>y>>d;upd1(x,y,d);}
		if(s=="Add"){int x,y,d;cin>>x>>y>>d;upd2(x,y,d);}
		if(s=="Change")
			{
			int x,d;cin>>x>>d;int qu;
			if(dep[q[x][0]]<dep[q[x][1]])qu=q[x][1];
			else qu=q[x][0];
			gai(dfn[qu],dfn[qu],1,1,n,d);
			}
		if(s=="Max"){int x,y;cin>>x>>y;cout<<query1(x,y)<<'\n';}
		}
	return 0;
	}