gistfile1.cpp

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define foreach(it, v) for (typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
const int MAX_N = 10005;
struct Node {
  int size, dist;
	bool isRoot;
	Node *fa, *ch[2];
	inline bool d() { return fa->ch[1] == this; }
	inline void setChild(Node *c, int d) {
		ch[d] = c;
		c->fa = this;
	}
	inline void up() { size = ch[0]->size + ch[1]->size + 1; }
	inline void rot() {
		bool o = d();
		Node *f = fa;
		if (f->isRoot) {
			f->isRoot = 0;
			isRoot = 1;
			fa = f->fa;
		} else {
			f->fa->setChild(this, f->d());
		}
		f->setChild(ch[!o], o);
		setChild(f, !o);
		f->up();
	}
	inline void Splay();
}mem[MAX_N], *null = &mem[0], *C, *pt[MAX_N];

void Node::Splay() {
	while (!isRoot) {
		if (fa->isRoot) {
			rot();
		} else {
			d() == fa->d() ? (fa->rot(), rot()) : (rot(), rot());
		}
	}
	up();
}

Node *select(Node *p, int k) {
	while (p->ch[0]->size + 1 != k) {
		if (p->ch[0]->size >= k) {
			p = p->ch[0];
		} else {
			k -= p->ch[0]->size + 1;
			p = p->ch[1];
		}
	}
	return p;
}

int n;
vector < pair <int, int> > E[MAX_N];

Node *newNode() {
	C->size = 1;
	C->fa = C->ch[0] = C->ch[1] = null;
	C->isRoot = 1;
	return C++;
}

void bfs() {
	static int Q[MAX_N];
	int qh = 0, qt = 1;
	Q[0] = 0;
	pt[0]->dist = 0;
	while (qh != qt) {
		int x = Q[qh++];
		foreach (it, E[x]) {
			if (it->first != pt[x]->fa - null - 1) {
				pt[it->first]->fa = pt[x];
				pt[it->first]->dist = pt[x]->dist + it->second;
				Q[qt++] = it->first;
			}
		}
	}
}

int X, Y, K;

int expose(Node *p, int t) {
	for (Node *tmp = null; p != null; tmp = p, p = p->fa) {
		p->Splay();
		if (t == 1 && p->fa == null) {
			return pt[X]->dist + pt[Y]->dist - 2 * p->dist;
		}
		if (t == 2 && p->fa == null) {
			if (p->ch[1]->size >= K) {
				Node *res = select(p->ch[1], p->ch[1]->size - K + 1);
				res->Splay();
				return res - null;
			} else if (p->ch[1]->size + 1 == K) {
				return p - null;
			} else {
				K -= p->ch[1]->size + 1;
				Node *res = select(tmp, K);
				res->Splay();
				return res - null;
			}
		}
		p->ch[1]->isRoot = 1;
		p->ch[1]->fa = p;
		p->setChild(tmp, 1);
		tmp->isRoot = 0;
		p->up();
	}
	return 0;
}

int main() {
	freopen("in", "r", stdin);
	int Tc;
	null->size = 0;
	null->fa = null->ch[0] = null->ch[1] = null;
	for (scanf("%d", &Tc); Tc--; ) {
		C = &mem[1];
		scanf("%d", &n);
		rep (i, n) {
			E[i].clear();
			pt[i] = newNode();
		}
		rep (i, n - 1) {
			int x, y, w;
			scanf("%d%d%d", &x, &y, &w);
			x--; y--;
			E[x].push_back(make_pair(y, w));
			E[y].push_back(make_pair(x, w));
		}
		bfs();
		for (char op[10]; scanf("%s", op) && !(op[0] == 'D' && op[1] == 'O'); ) {
			if (op[0] == 'D') {
				scanf("%d%d", &X, &Y);
				X--; Y--;
				expose(pt[X], 0);
				printf("%d\n", expose(pt[Y], 1));
			} else {
				scanf("%d%d%d", &X, &Y, &K);
				X--; Y--;
				expose(pt[X], 0);
				printf("%d\n", expose(pt[Y], 2));
			}
		}
	}
	return 0;
}