rt，RE了，用题解区大佬给的数据生成器拍了上千组数据也没问题，求助/kel

才一道蓝色树剖把我卡成这样我也是服了/kk >_<

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100010;
int head[N],to[N*2],nex[N*2],cnt,e[N*2];
void add(int x,int y,int z){
	cnt++;
	to[cnt]=y;
	e[cnt]=z;
	nex[cnt]=head[x];
	head[x]=cnt;
}
int T,n;
int dep[N],fa[N],sz[N],son[N],tp[N],tot,dfn[N];
int t[N];//边转点初始权值
int a[N];//建立在dfn上的权值
int p[N];//把dfn映射成点号
void dfs1(int x,int f){
	sz[x]=1;
	dep[x]=dep[f]+1;
	fa[x]=f;
	int maxn=-1;
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(y==f)
			continue;
		t[y]=e[i];
		dfs1(y,x);
		sz[x]+=sz[y];
		if(sz[y]>maxn){
			maxn=sz[y];
			son[x]=y;
		}
	}
}
void dfs2(int x,int top){
	tp[x]=top;
	tot++;
	dfn[x]=tot;
	p[tot]=x;
	a[tot]=t[x];
	if(son[x])
		dfs2(son[x],top);
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(y==fa[x]||y==son[x])
			continue;
		dfs2(y,y);
	}
}
int st[N*4];
void build(int root,int l,int r){
	if(l==r){
		st[root]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
	st[root]=st[root*2]+st[root*2+1];
}
int res;
int lca(int x,int y){
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]<dep[tp[y]])
			swap(x,y);
		x=fa[tp[x]];
	}
	if(dep[x]<dep[y])
		return x;
	return y;
}
void ask(int root,int l,int r,int x,int y){
	if(l>=x&&r<=y){
		res+=st[root];
		return;
	}
	int mid=(l+r)/2;
	if(mid>=x)
		ask(root*2,l,mid,x,y);
	if(mid+1<=y)
		ask(root*2+1,mid+1,r,x,y);
}
signed main(){
//	freopen("QTree2.in","r",stdin);
//	freopen("QTree2.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n;
		memset(head,0,sizeof(head));
		memset(son,0,sizeof(son));
		memset(sz,0,sizeof(sz));
		memset(nex,0,sizeof(nex));
		memset(dep,0,sizeof(dep));
		cnt=0;
		tot=0;
		for(int i=1;i<n;i++){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
		}
		dfs1(1,1);
		dfs2(1,1);
		build(1,1,n);
		string opt;
		while(cin>>opt){
			if(opt[1]=='O')
				break;
			if(opt[0]=='D'){
				int x,y;
				res=0;
				scanf("%lld%lld",&x,&y);
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]])
						swap(x,y);
					ask(1,1,n,dfn[tp[x]],dfn[x]);
					x=fa[tp[x]];
				}
				if(x!=y){
					if(dep[x]>dep[y])
						swap(x,y);
					ask(1,1,n,dfn[x]+1,dfn[y]);
				}
				printf("%lld\n",res);
			}
			else{
				int x,y,k;
				scanf("%lld%lld%lld",&x,&y,&k);
				int xx=x,yy=y;
				int LCA=lca(x,y);
				int d=dep[x]-dep[LCA]+1;
				int ans=-1;
				if(d>=k){
					while(ans==-1){
						if(dep[xx]-dep[tp[x]]+1<k)
							x=fa[tp[x]];
						else{
							ans=p[dfn[x]-k+dep[xx]-dep[x]+1];
							break;
						}
					}
				}
				else{
					k-=d;
					k=dep[y]-dep[LCA]-k+1;
					while(ans==-1){
						if(dep[yy]-dep[tp[y]]+1<k)
							y=fa[tp[y]];
						else{
							ans=p[dfn[y]-k+dep[yy]-dep[y]+1];
							break;
						}
					}
				}
				printf("%lld\n",ans);
			}
		}
	}
	return 0;
}