Skip to content

Instantly share code, notes, and snippets.

@edwardmjm
Created March 27, 2013 17:47
Show Gist options
  • Save edwardmjm/262878b00fa45e8eff5d to your computer and use it in GitHub Desktop.
Save edwardmjm/262878b00fa45e8eff5d to your computer and use it in GitHub Desktop.
SPOJ QTREE
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment