#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using
namespace std;
#define maxn 22000
int nn,n;
int
e[maxn],ne[maxn],v[maxn],fa[maxn],w[maxn];
void add(int x,int y,int z){
ne[++nn]=e[x],e[x]=nn,v[nn]=y,w[nn]=z;
}
struct node{
int
ch[2],s,val,pre,siz,rt;
}t[maxn];
#define c(x,y) t[x].ch[y]
void
up(int x){
t[x].siz=t[c(x,1)].siz+t[c(x,0)].siz+1;
t[x].s=t[c(x,1)].s+t[c(x,0)].s+t[x].val;
}
void init(){
t[0].s=t[0].siz=0;
memset(e,0,sizeof(e));
memset(fa,0,sizeof(fa));
nn=0;
for(int i=1;i<=n;i++){
t[i].pre=t[i].ch[0]=t[i].ch[1]=t[i].s=t[i].val=0;
t[i].rt=t[i].siz=1;
}
}
int qu[maxn],bo,he;
void rotate(int
x){
int y=t[x].pre,k=x==t[y].ch[0],z=t[y].pre;
t[y].ch[!k]=t[x].ch[k];
t[t[x].ch[k]].pre=y;
t[x].ch[k]=y;
t[y].pre=x;
t[x].pre=z;
if(!t[y].rt)t[z].ch[t[z].ch[1]==y]=x;
else t[y].rt=0,t[x].rt=1;
up(y);
}
void splay(int
x){
for(;!t[x].rt;){
int y=t[x].pre,z=t[y].pre;
if(t[y].rt)rotate(x);
else
if((t[z].ch[1]==y)==(t[y].ch[1]==x))rotate(y),rotate(x);
else
rotate(x),rotate(x);
}
up(x);
}
int acess(int x){
int
y=0;
for(;x;y=x,x=t[x].pre){
splay(x);
t[c(x,1)].rt=1;
t[c(x,1)=y].rt=0;
up(x);
}
return y;
}
int T;
int
find(int x,int k){
while(t[c(x,1)].siz+1!=k){
if(t[c(x,1)].siz>=k)x=c(x,1);
else
x=c(x,0),k-=(t[c(x,1)].siz+1);
}
return x;
}
int askk(int a,int
b,int k){
if(k==1)return a;
acess(a);
int
y=acess(b);
splay(a);
if(a==y){
if(k==t[c(a,1)].siz+1)return
b;
return find(c(a,1),t[c(a,1)].siz+2-k);
}
int
z=t[a].siz;
if(z+1==k)return y;
if(z>=k){
return
find(a,k);
}else{
return
find(c(y,1),t[c(y,1)].siz+2+z-k);
}
}
int askd(int a,int
b){
acess(a);
int y=acess(b);
splay(a);
if(a==y)return
t[c(y,1)].s;
return t[c(y,1)].s+t[a].s;
}
char in[10];
int
main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
init();
for(int
i=1;i<n;i++){
int a,b,g;
scanf("%d%d%d",&a,&b,&g);
add(a,b,g);
add(b,a,g);
}
qu[bo=he=1]=1;
while(he>=bo){
int
x=qu[bo++];
for(int i=e[x];i;i=ne[i]){
if(fa[x]==v[i])continue;
int y=v[i];
fa[y]=x;
t[y].pre=x;
t[y].val=t[y].s=w[i];
qu[++he]=y;
}
}
while(1){
scanf("%s",in);
if(in[1]==‘O‘)break;
if(in[1]==‘I‘){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",askd(a,b));
}else{
int a,b,g;
scanf("%d%d%d",&a,&b,&g);
printf("%d\n",askk(a,b,g));
}
}
}
}
原文：http://www.cnblogs.com/wangyucheng/p/3604096.html