QTREE2

QTREE2.cpp

#include <cstdio>
#include <algorithm>
const int N = 10009;
int f[N][15],dep[N],dist[N],n,ec,son[N],lnk[N * 2],nxt[N * 2],len[N * 2];
void dfs(const int u)
{
	for (int v,i = son[u]; i; i = nxt[i]) {
		if ((v = lnk[i]) == f[u][0]) continue;
		f[v][0] = u;
		dep[v] = dep[u] + 1;
		dist[v] = dist[u] + len[i];
		dfs(v);
	}
}
inline void addedge(const int x,const int y,const int z)
{
	nxt[++ec] = son[x];
	son[x] = ec;
	lnk[ec] = y;
	len[ec] = z;
}
int getlca(int x,int y)
{
	if (dep[y] > dep[x]) std::swap(x,y);
	for (int i = 14; i >= 0; --i)
		if (dep[f[x][i]] >= dep[y]) x = f[x][i];
	if (x == y) return x;
	for (int i = 14; i >= 0; --i)
		if (f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
	return f[x][0];
}
int getKth(int x,int k)
{
	for (int i = 0; k; ++i,k /= 2)
		if (k & 1) x = f[x][i];
	return x;
}
int main()
{
	int T = 0;
	scanf("%d",&T);
	while (T--) {
		scanf("%d",&n);
		for (int i = 1; i <= n; ++i) son[i] = 0;
		ec = 0;
		for (int x,y,z,i = 1; i < n; ++i) {
			scanf("%d%d%d",&x,&y,&z);
			addedge(x,y,z);
			addedge(y,x,z);
		}
		dep[1] = 1;
		dfs(1);
		for (int i = 1; i < 15; ++i)
			for (int j = 1; j <= n; ++j)
				f[j][i] = f[f[j][i - 1]][i - 1];
		char s[10];
		for (int x,y,z; scanf("%s",s),s[1] != 'O'; ) {
			scanf("%d%d",&x,&y);
			int lca = getlca(x,y);
			if (s[0] == 'D') printf("%d\n",dist[x] + dist[y] - 2 * dist[lca]);
			else {
				scanf("%d",&z);
				if (dep[x] - dep[lca] + 1 >= z) printf("%d\n",getKth(x,z - 1));
				else printf("%d\n",getKth(y,dep[x] + dep[y] - 2 * dep[lca] + 1 - z));
			}
		}
		puts("");
	}
}