SPOJ QTREE

gistfile1.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <bitset>
#include <queue>
#include <sstream>
#include <cassert>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define all(v) (v).begin(), (v).end()
#define iter(v) __typeof((v).begin())
#define foreach(it, v) for (iter(v) it = (v).begin(); it != (v).end(); it++)
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)(a); i <= (b); i++)
typedef long long ll;
typedef pair <int,int> PII;
template <class T> inline void checkmax(T &t, T x){if (x > t) t = x;}

const int N = 10005;
struct Node {
  int val, max;
	bool isRoot;
	Node *fa, *ch[2];
	inline bool d() { return fa->ch[1] == this; }
	inline void setChild(int d, Node *c) { ch[d] = c; c->fa = this; }
	inline void update();
	inline void Splay();
	inline void rot();
}mem[N], *null = &mem[0], *C, *pt[N]; //pt ---- map index to Node

void Node::update() {
	max = val;
	if (ch[0] != null) checkmax(max, ch[0]->max);
	if (ch[1] != null) checkmax(max, ch[1]->max);
}

void Node::rot() {
    bool o = d();
    Node *tmp = fa;
    if (!fa->isRoot) {
        fa->fa->setChild(fa->d(), this);
    } else {
        fa->isRoot = 0;
        isRoot = 1;
        fa = fa->fa;
    }
    tmp->setChild(o, ch[!o]);
    setChild(!o, tmp);
    tmp->update();
}
void Node::Splay() {
    while (!isRoot) {
        if (fa->isRoot) {
            rot();
        } else {
            d() == fa->d() ? fa->rot() : rot();
            rot();
        }
    }
    update();
}

int n;
int fa[N];
vector <PII> E[N];
map <PII, int> ref;
int edgePt[N];

inline Node *make() {
	C->val = C->max = 0x80000000;
	C->isRoot = 1;
	C->fa = C->ch[0] = C->ch[1] = null;
	return C++;
}

int Q[N];

void bfs() {
    int qh = 0, qt = 1;
    Q[0] = 0;
	rep (i, n) fa[i] = -1;
	while (qh != qt) {
		int x = Q[qh++];
		foreach (it, E[x]) {
			if (it->first != fa[x]) {
				fa[it->first] = x;
				pt[it->first]->fa = pt[x];
				pt[it->first]->val = it->second;
				pt[it->first]->update();
				edgePt[ref[mp(x, it->first)]] = it->first;
				Q[qt++] = it->first;
			}
		}
	}
}

inline void expose(Node *p, bool type) {
	Node *res = null;
	while (p != null) {
		p->Splay();
		if (p->fa == null && type)
		    printf("%d\n", max(res->max, p->ch[1]->max));
		p->ch[1]->isRoot = 1;
		p->ch[1]->fa = p;
		p->setChild(1, res);
		res->isRoot = 0;
		p->update();
		res = p;
		p = p->fa;
	}
}

int main() {
	int Tc;
	scanf("%d", &Tc);
	while (Tc--) {
		scanf("%d", &n);
		ref.clear();
		rep (i, n) E[i].clear();
		rep (i, n - 1) {
			int x, y, w;
			scanf("%d%d%d", &x, &y, &w);
			x--; y--;
			E[x].pb(mp(y, w));
			E[y].pb(mp(x, w));
			ref[mp(x, y)] = i;
			ref[mp(y, x)] = i;
		}
		null->val = null->max = 0x80000000;
		C = &mem[1];
		rep (i, n) pt[i] = make();
		bfs();
		for (char op[10]; scanf("%s", op) && op[0] != 'D'; ) {
			if (op[0] == 'C') {
				int i, x;
				scanf("%d%d", &i, &x);
				i = edgePt[i - 1];
				pt[i]->Splay();
				pt[i]->val = x;
				pt[i]->update();
			} else if (op[0] == 'Q') {
				int x, y;
				scanf("%d%d", &x, &y);
				x--; y--;
			    expose(pt[x], 0);
                expose(pt[y], 1);
			}
		}
	}
	return 0;
}