SPOJ QTREE-Query on a tree

QTREE - Query on a 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      

題意：有一棵樹，有兩個操作，一種是改變某條邊的權值，一種是查詢點u到v之間的路徑的最大邊權

解題思路：樹鍊剖分，邊權給點權即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <bitset>
#include <set>
#include <vector>
#include <functional>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;

int n, x, y, z;
int s[200009], nt[200009], e[200009], v[200009], cnt;
int ct[200009], mx[200009], fa[200009], dep[200009];
int top[200009], g[200009], G[200009], G1[200009], a[200009], ma[200009 << 2];
char ch[10];

void dfs(int x, int f)
{
	dep[x] = dep[f] + 1;
	fa[x] = f; ct[x] = 1; mx[x] = 0;
	for (int i = s[x]; ~i; i = nt[i])
	{
		if (e[i] == f) continue;
		dfs(e[i], x);
		ct[x] += ct[e[i]];
		if (ct[e[i]] > ct[mx[x]]) mx[x] = e[i];
	}
}

void Dfs(int x, int t)
{
	top[x] = !t ? x : top[fa[x]];
	g[x] = ++cnt;
	if (mx[x]) Dfs(mx[x], 1);
	for (int i = s[x]; ~i; i = nt[i])
	{
		if (e[i] == fa[x]) continue;
		if (e[i] == mx[x]) { G[g[e[i]]] = v[i]; G1[v[i]] = g[e[i]]; continue; }
		Dfs(e[i], 0);
		G[g[e[i]]] = v[i];
		G1[v[i]] = g[e[i]];
	}
}

void build(int k, int l, int r)
{
	if (l == r) { ma[k] = a[G[l]]; return; }
	int mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	ma[k] = max(ma[k << 1], ma[k << 1 | 1]);
}

void update(int k, int l, int r, int p, int val)
{
	if (l == r) { ma[k] = val; return; }
	int mid = (l + r) >> 1;
	if (p <= mid) update(k << 1, l, mid, p, val);
	else update(k << 1 | 1, mid + 1, r, p, val);
	ma[k] = max(ma[k << 1], ma[k << 1 | 1]);
}

int query(int k, int l, int r, int ll, int rr)
{
	if (l >= ll&&r <= rr) return ma[k];
	int ans = 0;
	int mid = (l + r) >> 1;
	if (ll <= mid) ans = max(ans, query(k << 1, l, mid, ll, rr));
	if (rr > mid) ans = max(ans, query(k << 1 | 1, mid + 1, r, ll, rr));
	return ans;
}

int getans(int x, int y)
{
	int ans = 0;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans = max(ans, query(1, 1, n, g[top[x]], g[x])); x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	if (x == y) return ans;
	return max(ans, query(1, 1, n, g[x] + 1, g[y]));
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		memset(s, -1, sizeof s);
		dep[0] = ct[0] = cnt = 0;
		for (int i = 1; i < n; i++)
		{
			scanf("%d%d%d", &x, &y, &a[i]);
			nt[cnt] = s[x], s[x] = cnt, v[cnt] = i, e[cnt++] = y;
			nt[cnt] = s[y], s[y] = cnt, v[cnt] = i, e[cnt++] = x;
		}
		dfs(1, 0);
		Dfs(1, cnt = 0);
		build(1, 1, n);
		while (scanf("%s", ch) && ch[0] != 'D')
		{
			scanf("%d%d", &x, &y);
			if (ch[0] == 'C') update(1, 1, n, G1[x], y);
			else printf("%d\n", getans(x, y));
		}
	}
	return 0;
}