题意：
一颗树上，两种操作，一种问两点的距离，另一个问路上第k个节点编号
思路：
距离可以很简单地求，求第k个节点编号，我们可以把路径切成两段，一段是u到LCA，一段是LCA到v，那么我们看一下k属于哪一段，就能用常规的倍增去求那个点了
错误及反思：
代码：
#include<bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int N = 10100;
struct EDGE{int to,next,val;
}e[N*2];
int tot,n,T;
int point[N][20],val[N][20],depth[N],fi[N],fa[N],;
char ta[10];
void addedge(int x,int y,int z)
{e[tot].to=y;e[tot].val=z;e[tot].next=fi[x];fi[x]=tot++;e[tot].to=x;e[tot].val=z;e[tot].next=fi[y];fi[y]=tot++;
}
void init()
{tot=0;memset(fi,-1,sizeof(fi));
}
void dfs(int now,int fa,int de){depth[now]=de;point[now][0]=fa;for(int i=fi[now];i!=-1;i=e[i].next)if(e[i].to!=fa){val[e[i].to][0]=e[i].val;dfs(e[i].to,now,de+1);}
}
void getlca()
{for(int i=1;i<=14;i++){for(int j=1;j<=n;j++){point[j][i]=point[point[j][i-1]][i-1];val[j][i]=val[j][i-1]+val[point[j][i-1]][i-1];}}
}void solve(int a,int b){if(depth[a]>depth[b])swap(a,b);int ans=0;for(int i=14;i>=0;i--)if(depth[point[b][i]]>=depth[a]){ans+=val[b][i];b=point[b][i];}if(a!=b){for(int i=14;i>=0;i--){if(point[a][i]!=point[b][i]){ans+=val[a][i]+val[b][i];a=point[a][i];b=point[b][i];}}}if(a!=b) ans+=val[a][0]+val[b][0];printf("%d\n",ans);
}
int lca(int a,int b){if(depth[a]>depth[b])swap(a,b);for(int i=14;i>=0;i--)if(depth[point[b][i]]>=depth[a])b=point[b][i];if(a==b) return a;for(int i=14;i>=0;i--){if(point[a][i]!=point[b][i]){a=point[a][i];b=point[b][i];}}return point[a][0];
}
int main(){scanf("%d",&T);while(T--){init();scanf("%d",&n);for(int i=0,u,v,w;i<n-1;i++){scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);}dfs(1,1,1);getlca();while(scanf("%s",ta)&&ta[1]!='O'){if(ta[1]=='I'){int tb,tc;scanf("%d%d",&tb,&tc);solve(tb,tc);}else{int tb,tc,k;scanf("%d%d%d",&tb,&tc,&k);int LCA=lca(tb,tc);if(depth[tb]-depth[LCA]+1>=k){k--;int now=0;while(k){if(k&1) tb=point[tb][now];k/=2;now++;}printf("%d\n",tb);}else{k-=depth[tb]-depth[LCA]+1;k=depth[tc]-depth[LCA]-k;int now=0;while(k){if(k&1) tc=point[tc][now];k/=2;now++;}printf("%d\n",tc);}}}}
}