题目链接【http://www.spoj.com/problems/QTREE/】
题意：给出一个包含N(N<=10000)节点的无根树，有多次询问，询问的方式有两种1、DIST a b 求a->b之间的距离。2、KTH a b k 求a->b链上的第k个节点是谁，。如果输入DONE,结束询问。
思路：首先想到用倍增法可以解决第一种询问，只需要在DFS时候维护一个dis[i]（表示i节点到根节点之间的距离，因为是无根树，我们定义节点1为根），dis(a->b)=dis[a]+dis[b]-dia[lca(a,b)]。第二种询问的解法是首先求出a,b的lca,然后根据lca到a到b的深度判断第k个数在左半枝还是右半枝（可以定义lca为左半枝），然后用倍增的方法求出第k个节点。
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = ;
struct node
{
int id, len, next;
} E[maxn << ];
int p[maxn << ], num;
void init()
{
memset(p, -, sizeof(p));
num = ;
}
void add(int u, int v, int dis)
{
E[num].id = u;
E[num].len = dis;
E[num].next = p[v];
p[v] = num++;
}
//------------------------------------------邻接表
int T, N;
int fa[][maxn];//倍增数组
int dis[maxn], dep[maxn];//距离，深度数组
void DFS(int u, int FA)//DFS求出每个节点的深度，每个节点到根节点的距离，和每个节点跳1步到达的位置
{
for(int l = p[u]; l != -; l = E[l].next)
{
int id = E[l].id;
if(id == FA) continue;
fa[][id] = u;
dep[id] = dep[u] + ;
dis[id] = dis[u] + E[l].len;
DFS(id, u);
}
}
void INIT()//初始化倍增数组
{
memset(fa, -, sizeof(fa));
memset(dis, , sizeof(dis));
memset(dep, , sizeof(dep));
DFS(, -);
for(int k = ; k + <= ; k++)
{
for(int u = ; u <= N; u++)
{
if(fa[k][u] < )
fa[k + ][u] = -;
else
fa[k + ][u] = fa[k][fa[k][u]];
}
}
}
int LCA(int u, int v)
{
if(dep[u] > dep[v]) swap(u, v);
for(int k = ; k <= ; k++)//微调，使得dep相等
if((dep[v] - dep[u]) >> k & )
v = fa[k][v];
if(u == v) return u;//公共祖先是u，v中的其中一个
for(int k = ; k >= ; k--)//一起向上跳，先跳距离远的
{
if(fa[k][u] != fa[k][v])
{
u = fa[k][u];
v = fa[k][v];
}
}
return fa[][u];
}
int KTH(int u, int v, int lca, int k)//从u->v路径上的第k个数
{
if(k == ) return u;
int l1 = dep[u] - dep[lca] + ;//左半枝
int l2 = dep[v] - dep[lca];
if(k <= l1)//在左半枝（lca定义成左半枝）
{
k -= ;
for(int t = ; t >= ; t--)
{
if(k >> t & )
u = fa[t][u];
}
return u;
}
else//在右半枝
{
k -= l1;
k = l2 - k;
for(int t = ; t >= ; t--)
{
if(k >> t & )
v = fa[t][v];
}
return v;
}
}
int main ()
{
scanf("%d", &T);
while(T--)
{
init();
int u, v, ds, k;
char s[];
scanf("%d", &N);
for(int i = ; i < N; i++)
{
scanf("%d%d%d", &u, &v, &ds);
add(u, v, ds);
add(v, u, ds);
}
INIT();
while(scanf("%s", s))
{
if(!strcmp(s, "DONE"))
break;
else if(!strcmp(s, "DIST"))
{
scanf("%d%d", &u, &v);
printf("%d\n", dis[u] + dis[v] - * dis[LCA(u, v)]);
}
else
{
scanf("%d%d%d", &u, &v, &k);
int lca = LCA(u, v);
printf("%d\n", KTH(u, v, lca, k)); }
}
}
return ;
}