原题:
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.
We will ask you to perfrom some instructions of the following form:
The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.
For each test case:
There is one blank line between successive tests.
For each "QUERY" operation, write one integer representing its result.
Input: 1 3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE Output: 1 3
裸的树链剖分
code:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define REP(i, l, r) for (int i = l; i >= r; i--)
#define INF 19971228
#define MAXN 1010
int n, m = 0, root, N = -1, siz[MAXN], dep[MAXN], son[MAXN], fat[MAXN], top[MAXN], w[MAXN], first[MAXN], next[MAXN], num[MAXN], sb[MAXN];
int bh[MAXN], M = 0, edg[MAXN];
struct tlist{int x, y, t;} a[MAXN];
bool vis[MAXN];
struct Tree{int l, r, mx, lc, rc;} tree[MAXN];
inline void add(int x, int y, int t) {a[++N].x = x, a[N].y = y, a[N].t = t, next[N] = first[x], first[x] = N;}
inline int min(int a, int b) {return a<b ? a : b;}
inline int max(int a, int b) {return a>b ? a : b;}
inline void dfs(int x, int DEP) {
siz[x] = 1;
dep[x] = DEP;
vis[x] = 1;
int maxsize = 0;
for (int i = first[x]; ~i; i = next[i])
if (!vis[a[i].y]) {
fat[a[i].y] = x;
edg[a[i].y] = i;
dfs(a[i].y, DEP+1);
siz[x] += siz[a[i].y];
if (siz[a[i].y] > maxsize) maxsize = siz[a[i].y], son[x] = a[i].y, sb[x] = i;
}
}
inline void DFS(int x, int T) {
vis[x] = 1;
top[x] = T;
if (son[x]) w[sb[x]] = ++m, num[m] = sb[x], DFS(son[x], T);
for (int i = first[x]; ~i; i = next[i])
if (!vis[a[i].y])
w[i] = ++m, num[m] = i, DFS(a[i].y, a[i].y);
}
inline void build_tree(int i, int L, int R) {
tree[i].l = L, tree[i].r = R;
if (L == R) {tree[i].mx = a[num[L]].t; return;}
build_tree(tree[i].lc = ++M, L, (L+R) >> 1);
build_tree(tree[i].rc = ++M, ((L+R) >> 1) + 1, R);
tree[i].mx = max(tree[tree[i].lc].mx, tree[tree[i].rc].mx);
}
inline void modify(int i, int x, int cx) {
int L = tree[i].l, R = tree[i].r;
if (x < L || x > R) return;
if (L == R) {tree[i].mx = cx; return;}
modify(tree[i].lc, x, cx);
modify(tree[i].rc, x, cx);
tree[i].mx = max(tree[tree[i].lc].mx, tree[tree[i].rc].mx);
}
inline int query(int i, int ql, int qr) {
int L = tree[i].l, R = tree[i].r;
if (qr < L || ql > R) return -INF;
if (ql <= L && qr >= R) return tree[i].mx;
return max(query(tree[i].lc, ql, qr), query(tree[i].rc, ql, qr));
}
inline int get_edge(int i) {return w[bh[i]] ? w[bh[i]] : w[bh[i]+1];}
int main() {
cin >> n;
memset(first, -1, sizeof(first));
memset(next, -1, sizeof(next));
rep(i, 1, n-1) {
int tx, ty, tt;
scanf("%d%d%d", &tx, &ty, &tt);
fat[ty] = tx;
if (!fat[tx]) root = tx;
bh[i] = N + 1;
add(tx, ty, tt);
add(ty, tx, tt);
}
memset(vis, 0, sizeof(vis));
dfs(root, 1);
memset(vis, 0, sizeof(vis));
memset(w, 0, sizeof(w));
memset(num, 0, sizeof(num));
DFS(root, root);
build_tree(M = 1, 1, m);
while (1) {
char ch[MAXN];
int tx, ty;
scanf("%s%d%d", ch, &tx, &ty);
if (ch[0] == 'D') break;
if (ch[0] == 'C') modify(1, get_edge(tx), ty);
if (ch[0] == 'Q') {
int f1, f2, ans = -INF;
while (tx != ty) {
f1 = top[tx], f2 = top[ty];
if (f1 != f2) {
if (dep[f1] < dep[f2]) swap(f1, f2), swap(tx, ty);
ans = max(ans, query(1, w[edg[f1]], w[edg[tx]])), tx = fat[f1];
}
else {
if (dep[tx] < dep[ty]) swap(tx, ty);
ans = max(ans, query(1, w[edg[son[ty]]], w[edg[tx]])), tx = ty;
}
}
cout << ans << endl;
}
}
return 0;
}
kyeremal-spoj375-Query on a tree-树链剖分
原文：http://blog.csdn.net/kyeremal/article/details/45774907