題意：
給你一棵N個點的樹要求支持兩種操作：
DIST a b 求a到b路徑距離
KTH a b k 求a到b路徑上的第k個節(jié)點
做法：
還是動態(tài)樹..跟QTREE本質沒什么差別
對于DIST 兩次拉實然后求兩段的Sum
KTH便是兩次拉實后分情況討論（在左邊還是右邊還是正好那個LCA)
PS:
如果本題改成求a到b路徑上第k大的數(shù)字，那便是CTSC難度的了。。（network）
1
#include <cstdio>
2#include <cstring>
3#define n 100005
4struct Tsplay
5
{
6
#define Par(x) (T[x].p)
7 #define Lch(x) (T[x].l)
8 #define Rch(x) (T[x].r)
9 #define Val(x) (T[x].val)
10 #define Sum(x) (T[x].sum)
11 #define Size(x) (T[x].size)
12 #define Root(x) (Lch(Par(x))!=x&&Rch(Par(x))!=x)
13 int l,r,p;
14 int val,sum,size;
15
} T[n];
16int vtx[200005],w[200005],ne[200005],L[n],q[n],tot,N;
17bool vis[n];
18char cmd[1005];
19inline void Ins(int u,int v,int ww)
20{
21 vtx[++tot]=v;w[tot]=ww;ne[tot]=L[u];L[u]=tot;
22}
23inline void BuildTree()
24{
25 memset(vis,0,sizeof(vis));
26 vis[q[1]=1]=1;
27 for (int h=1,t=1,u=q[1];h<=t;u=q[++h])
28 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
29 if (!vis[v]) Par(v)=u,Size(v)=1,Val(v)=w[p],vis[q[++t]=v]=1;
30}
31inline int Findkth(int root,int k)
32{
33 for (int p=root;;)
34 if (k<=Size(Lch(p))) p=Lch(p);
35 else
36 if (k<=Size(Lch(p))+1) return p;
37 else k-=Size(Lch(p))+1,p=Rch(p);
38}
39inline void Tupdate(int x)
40{
41 Size(x)=Size(Lch(x))+1+Size(Rch(x));
42 Sum(x)=Val(x);
43 if (Lch(x)) Sum(x)+=Sum(Lch(x));
44 if (Rch(x)) Sum(x)+=Sum(Rch(x));
45}
46inline void zig(int x)
47{
48 int y=Par(x),z=Par(y);
49 Lch(y)=Rch(x),Par(Lch(y))=Rch(x)=y;
50 if (Lch(z)==y) Lch(z)=x;
51 else
52 if (Rch(z)==y) Rch(z)=x;
53 Par(x)=z,Par(y)=x;
54 Tupdate(y);
55}
56inline void zag(int x)
57{
58 int y=Par(x),z=Par(y);
59 Rch(y)=Lch(x),Par(Rch(y))=Lch(x)=y;
60 if (Lch(z)==y) Lch(z)=x;
61 else
62 if (Rch(z)==y) Rch(z)=x;
63 Par(x)=z,Par(y)=x;
64 Tupdate(y);
65}
66inline void splay(int x)
67{
68 for (int y,z;!Root(x);)
69
{
70 y=Par(x),z=Par(y);
71 if (Root(y))
72 if (Lch(y)==x) zig(x);
73 else zag(x);
74 else
75 if (Lch(z)==y)
76 if (Lch(y)==x) zig(y),zig(x);
77 else zag(x),zig(x);
78 else
79 if (Rch(y)==x) zag(y),zag(x);
80 else zig(x),zag(x);
81
}
82 Tupdate(x);
83}
84inline void Expose(int x)
85{
86 for (int u=x,v=0;u;u=Par(u))
87 splay(u),Rch(u)=v,Tupdate(v=u);
88}
89inline void Query(int x,int y,int k)
90{
91 Expose(y);
92 for (int u=x,v=0;u;u=Par(u))
93 {
94 if (splay(u),!Par(u))
95 {
96 if (!k) printf("%d\n",Sum(Rch(u))+Sum(v));
97 else
98 if (k<=Size(v)) printf("%d\n",Findkth(v,Size(v)-k+1));
99 else
100 if (k<=Size(v)+1) printf("%d\n",u);
101 else printf("%d\n",Findkth(Rch(u),k-Size(v)-1));
102 return;
103 }
104 Rch(u)=v,Tupdate(v=u);
105 }
106}
107int main()
108{
109 int Te,x,y,w,k;
110 for (scanf("%d",&Te);Te--;)
111 {
112 memset(L,0,sizeof(L));
113 tot=0;
114 scanf("%d",&N);
115 for (int i=0;i<=N;++i)
116 Par(i)=Lch(i)=Rch(i)=0;
117 for (int i=1;i<N;++i)
118 {
119 scanf("%d%d%d",&x,&y,&w);
120 Ins(x,y,w),Ins(y,x,w);
121 }
122 BuildTree();
123 for (;;)
124 {
125 scanf("%s",cmd);
126 if (cmd[1]=='O') break;
127 scanf("%d%d",&x,&y);
128 if (cmd[0]=='D') Query(x,y,0);
129 else scanf("%d",&k),Query(x,y,k);
130 }
131 }
132 return 0;
133}
134