刚学树链剖分
老是t
代码：

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=1<<14,M=1<<15;
struct graph{
	int edhead[N],ednxt[M],edw[M],edto[M],edtot=0;
	void addedge(int u,int v,int w){
		edtot++;
		edw[edtot]=w;
		ednxt[edtot]=edhead[u];
		edto[edtot]=v;
		edhead[u]=edtot;
	}
	void clear(){
		mem(edhead,0);
		edtot=0;
	}
}tree;
struct sgt{
#define mid(l,r) ((l+r)>>1)
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
	int val[M];
	void pu(int p){
		val[p]=max(val[lc(p)],val[rc(p)]);
	}
	void build(int p,int l,int r,int *arr){
		if(l==r){
			val[p]=arr[l];
			return;
		}
		build(lc(p),l,mid(l,r),arr);
		build(rc(p),mid(l,r)+1,r,arr);
		pu(p);
	}
	void change(int p,int l,int r,int pos,int v){
		if(l==r){
			val[p]=v;
			return;
		}
		if(pos<=mid(l,r)){
			change(lc(p),l,mid(l,r),pos,v);
		}else{
			change(rc(p),mid(l,r)+1,r,pos,v);
		}
		pu(p);
	}
	int query(int p,int l,int r,int ll,int rr){
		if(ll<=l&&r<=rr){
			return val[p];
		}
		if(rr<=mid(l,r)){
			return query(lc(p),l,mid(l,r),ll,rr);
		}else if(ll>mid(l,r)){
			return query(rc(p),mid(l,r)+1,r,ll,rr);
		}else{
			return max(query(rc(p),mid(l,r)+1,r,ll,rr),query(lc(p),l,mid(l,r),ll,rr));
		}
	}
#undef lc
#undef rc
#undef mid
}sgtree;
#define graph_go(g,p) for(int i=g.edhead[p],to=g.edto[i];i;i=g.ednxt[i],to=g.edto[i])
int w[N],son[N],f[N],dep[N],top[N],sz[N],toson[N],tot,n,mp[M],rmap[M],edval[M];
void dfs1(int p,int fa){
	f[p]=fa;
	son[p]=0;
	sz[p]=1;
	graph_go(tree,p){
		if(to==fa)continue;
		dep[to]=dep[p]+1;
		dfs1(to,p);
		sz[p]+=sz[to];
		if(sz[to]>sz[son[p]]){
			son[p]=to;
			toson[p]=(i+1)>>1;
		}
	}
}
void dfs2(int p,int tp,int ed){
	top[p]=tp;
	w[p]=++tot;
	mp[ed]=tot;
	rmap[tot]=ed;
	if(son[p])dfs2(son[p],tp,toson[p]);
	graph_go(tree,p){
		if(to==f[p]||to==son[p])continue;
		dfs2(to,to,(i+1)>>1);
	}
}
int qry(int x,int y){
	int ret=0,top1=top[x],top2=top[y];
	while(top1!=top2){
		if(dep[top1]<dep[top2])swap(top1,top2),swap(x,y);
		ret=max(ret,sgtree.query(1,1,n,w[top1],w[x]));
		x=f[top1];
		top1=top[x];
	}
	if(x==y)return ret;
	if(dep[x]<dep[y])swap(x,y);
	return max(ret,sgtree.query(1,1,n,w[son[y]],w[x]));
}
void cg(int a,int b){
	sgtree.change(1,1,n,mp[a],b);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		tot=0;
		tree.clear();
		cin>>n;
		for(int i=1;i<n;i++){
			int u,v,w;
			cin>>u>>v>>w;
			tree.addedge(u,v,w);
			tree.addedge(v,u,w);
		}
		dep[1]=1;
		dfs1(1,0);
		dfs2(1,1,0);
		for(int i=1;i<=n;i++){
			edval[i]=tree.edw[2*rmap[i]];
		}
		sgtree.build(1,1,n,edval);
		string op;
		int op1,op2;
		while(cin>>op&&op!="DONE"){
			cin>>op1>>op2;
			if(op=="QUERY"){
				cout<<qry(op1,op2)<<endl;
			}else{
				cg(op1,op2);
			}
		}
	}
}

哪位巨佬能帮帮我