Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment