代码如下：

// Problem: SP913 QTREE2 - Query on a tree II
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP913
// Memory Limit: 1500 MB
// Time Limit: 433 ms
// Date: 2023-01-02 23:13:23
// Author: fzy
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn=1e4+10;
const int inf=1e9+7;
int t,n,ans,st[maxn][26],in[maxn],dep[maxn],sum[maxn][26],num[maxn];
struct node{
	int u,dis;
};
vector<node> g[maxn];

inline int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

inline void dfs(int u) {
	for(int i=1;i<=25;++i)
		st[u][i]=st[st[u][i-1]][i-1],sum[u][i]=sum[u][i-1]+sum[st[u][i-1]][i-1];
	for(int i=0;i<(int)g[u].size();++i) {
		int v=g[u][i].u;
		int w=g[u][i].dis;
		if(v==st[u][0]) continue;
		dep[v]=dep[u]+1;
		sum[v][0]=w;
		st[v][0]=u;
		dfs(v);
	}
}

inline int lca1(int a,int b) {
	int ans=0;
	if(dep[a]<dep[b]) swap(a,b);
	for(int i=25;i>=0;--i) {
		if(dep[st[a][i]]>=dep[b]) {
			a=st[a][i];
			ans+=sum[a][i];
		}
	}
	if(a==b) return ans;
	for(int i=25;i>=0;--i) {
		if(st[a][i]!=st[b][i]) {
			ans+=sum[a][i];
			ans+=sum[b][i];
			a=st[a][i];
			b=st[b][i];
		}
	}
	return ans+sum[a][0]+sum[b][0];
}

inline int lcadep(int a,int b) {
	if(dep[a]<dep[b]) swap(a,b);
	for(int i=25;i>=0;--i) {
		if(dep[st[a][i]]>=dep[b]) {
			a=st[a][i];
		}
	}
	if(a==b) return dep[a];
	for(int i=25;i>=0;--i) {
		if(st[a][i]!=st[b][i]) {
			a=st[a][i];
			b=st[b][i];
		}
	}
	return dep[st[a][0]];
}

signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	t=read();
	while(t--) {
		int rt=0;
		memset(st,0,sizeof st);
		memset(in,0,sizeof in);
		memset(dep,0,sizeof dep);
		memset(sum,0,sizeof sum);
    	n=read();
		for(int i=1;i<n;++i) {
			int u=read(),v=read(),w=read();
			in[v]++;
			g[u].push_back(node{v,w});
			g[v].push_back(node{u,w});
		}
		for(int i=1;i<=n;++i) 
			if(in[i]==0) {
				rt=i;
				break;
			}
		dep[rt]=1;
		dfs(rt);
		// cout<<st[4][0]<<endl;
		string str;
		while(cin>>str) {
			if(str=="DONE") break;
			if(str=="DIST") {
				int a=read(),b=read();
				write(lca1(a,b)),puts("");
			}
			else {
				int a=read(),b=read(),k=read();
				int x=dep[a],y=dep[b],z=lcadep(a,b);
				int cnt=0;
				if(k<=x-z+1) {
					k--;
					while(k) {
						if(k%2==1) a=st[a][cnt];
						k/=2;
						cnt++;
					}
					write(a),puts("");
				}
				else {
					int tmp=x+y-2*z-k+1;
					while(tmp) {
						if(tmp%2==1) b=st[b][cnt];
						tmp/=2;
						cnt++;
					}
					write(b),puts("");
				}
			}
		}
	}
    return 0;
}