附代码:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000+10;
int T,n,f[MAXN][30],qzh[MAXN],dep[MAXN],lg[40];
vector<pair<int,int> >G[MAXN];
inline bool id(const char ch){
return ch>='0'&&ch<='9';
}
inline int read(void) {
int s=0;
char ch=getchar();
while(!id(ch)) ch=getchar();
while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
void dfs(const int k) {
for(int i=0;i<G[k].size();i++) {
if(G[k][i].first!=f[k][0]) {
f[G[k][i].first][0]=k;
for(int j=1;j<=20;j++) f[G[k][i].first][j]=f[k][j-1];
qzh[G[k][i].first]=qzh[k]+G[k][i].second;
dep[G[k][i].first]=dep[k]+1;
dfs(G[k][i].first);
}
}
return;
}
inline int cl(int u,int dp) {
int xl=0;
while(dp) {
if(dp&1) u=f[u][xl];
xl++,dp>>=1;
}
return u;
}
inline int lca(int u,int v) {
if(dep[u]<dep[v]) swap(u,v);
int k=dep[u]-dep[v];
u=cl(u,k);
if(u==v) return v;
for(int i=lg[v];i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
return f[u][0];
}
inline void work(void) {
for(int i=0;i<MAXN;i++) G[i].clear();
memset(f,0,sizeof(f)),memset(dep,0,sizeof(dep)),memset(qzh,0,sizeof(qzh));
n=read();
for(int i=1,a,b,c;i<n;i++)
a=read(),b=read(),c=read(),G[a].push_back(make_pair(b,c)),G[b].push_back(make_pair(a,c));
for(int i=0;i<20;i++) f[1][i]=1;
dep[1]=1;
dfs(1);
string tp;
int u,v,k;
while(cin>>tp) {
if(tp=="DONE") return;
if(tp=="DIST") {
u=read(),v=read();
int lc=lca(u,v);
printf("%d\n",qzh[u]+qzh[v]-2*qzh[lc]);
}
if(tp=="KTH") {
u=read(),v=read(),k=read();
int lc=lca(u,v);
int lcbh=dep[u]-dep[lc]+1;
if(k<=lcbh) printf("%d\n",cl(u,k-1));
else printf("%d\n",cl(v,dep[u]+dep[v]-2*dep[lc]+1-k));
}
}
cout<<'\n';
}
int main() {
lg[1]=0;
for(int i=2;i<MAXN;i++) lg[i]=lg[i/2]+1;
T=read();
while(T--) work();
return 0;
}