SPOJ-375 QTREE - Query on a tree (樹鍊剖分 邊權轉點權)

QTREE - Query on a tree

#tree

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:

• CHANGE i ti : change the cost of the i-th edge to ti

  or

• QUERY a b : ask for the maximum edge cost on the path from node a to node b

Input

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

• In the first line there is an integer N (N <= 10000),
• In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),
• The next lines contain instructions "CHANGE i ti" or "QUERY a b",
• The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.

Output

For each "QUERY" operation, write one integer representing its result.

Example

Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3      

#include <bits/stdc++.h>
using namespace std;
#define maxn 10004
vector<vector<int> >g(maxn);
struct edge{
	int from, to, val;
}a[maxn];
int c[maxn << 2], sz[maxn], id[maxn], dep[maxn], son[maxn], top[maxn],  pre[maxn], val[maxn], tot;
void dfs(int x, int fa, int d){
	sz[x] = 1;
	pre[x] = fa;
	dep[x] = d;
	son[x] = 0;
	int cur;
	for(int i = 0; i < g[x].size(); ++i){
		cur = g[x][i];
		if(cur == fa) continue;
		dfs(cur, x, d + 1);
		sz[x] += sz[cur];
		if(sz[son[x]] < sz[cur]){
			son[x] = cur;
		}
	}
}
void dfs1(int x, int tp){
	id[x] = ++tot;
	top[x] = tp;
	if(son[x]) dfs1(son[x], tp);
	int cur;
	for(int i = 0; i < g[x].size(); ++i){
		cur = g[x][i];
		if(cur == pre[x] || cur == son[x]) continue;
		dfs1(cur, cur);
	}
}
void build(int o, int l, int r){
	if(l == r){
		c[o] = val[l];
		return;
	}
	int mid = l + r >> 1;
	build(o << 1, l, mid);
	build(o << 1 | 1, mid + 1, r);
	c[o] = max(c[o << 1], c[o << 1 | 1]);
}
int query(int o, int l, int r, int L, int R){
	if(l >= L & r <= R){
		return c[o];
	}
	int mid = l + r >> 1, ans = -1e9;
	if(mid >= L) ans = max(ans, query(o << 1, l, mid, L, R));
	if(mid < R) ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
	return ans;
}
int getmx(int x, int y){
	int tp1 = top[x], tp2 = top[y];
	int ans = -1e9;
	while(tp1 != tp2){
		if(dep[tp1] < dep[tp2]){
			swap(tp1, tp2);
			swap(x, y);
		}
		ans = max(ans, query(1, 1, tot, id[tp1], id[x]));
		x = pre[tp1];
		tp1 = top[x];
	}
	if(x != y){
		if(dep[x] < dep[y]) swap(x, y);
		ans = max(ans, query(1, 1, tot, id[son[y]], id[x]));
	}
	return ans;
}
void add(int o, int l, int r, int pos, int v){
	if(l == r){
		c[o] = v;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) add(o << 1, l, mid, pos, v);
	else add(o << 1 | 1, mid + 1, r, pos, v);
	c[o] = max(c[o << 1], c[o << 1 | 1]);
}
int main(){
	int T, n, u, v, x;
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i){
			g[i].clear();
		}
		for(int i = 1; i <= n; ++i){
			scanf("%d %d %d", &u, &v, &x);
			g[u].push_back(v);
			g[v].push_back(u);
			a[i].from = u;
			a[i].to = v;
			a[i].val = x;
		}
		tot = 0;
		dfs(1, 0, 1);
		dfs1(1, 1);
		for(int i = 1; i <= n; ++i){
			if(dep[a[i].from] < dep[a[i].to]){
				swap(a[i].from, a[i].to);
			}
			val[id[a[i].from]] = a[i].val;
		}
		build(1, 1, tot);
		char s[10];
		while(scanf("%s", s) != EOF){
			if(s[0] == 'D'){
				break;
			}
			if(s[0] == 'Q'){
				scanf("%d %d", &u, &v);
				printf("%d\n", getmx(u, v));
			}
			if(s[0] == 'C'){
				scanf("%d %d", &u, &v);
				a[u].val = v;
				add(1, 1, tot, id[a[u].from], v);
			}
		}
	}
}

/*
題意：一棵樹，1e4個點，每條邊有邊權，然後多次操作，每次操作要麼修改某條邊的邊權，
要麼查詢兩點之間路徑上邊權最大值。

思路：樹鍊剖分的模闆題了。唯一不同的是這次權值是在邊上，這樣我們把每一條邊的邊權轉移
記錄到深度較大的點上，因為每個點向上隻有一條邊，向下可能有多條邊。這樣我們就還是對點操作了。
注意最後tp1 == tp2時，可能x != y,這樣我們還需要查詢x和y之間的邊，因為我們的記錄方式是把邊
值轉移到深度較大的點上，是以y下面的那條邊記錄在son[y]上。為什麼是son[y]而不是别的兒子呢？
如果x和y在lca的兩邊，那麼tp1 == tp2時，x一定等于y。如果x或y是lca就有可能會發生tp1 == tp2時x != y
的情況，tp1 == tp2說明最後x,y的top值相同，說明它們在一條重鍊上，是以是son[y]。
*/