Tree POJ - 3237（树链剖分+线段树（懒惰标记））

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

1

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

Sample Output

1
3

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100010;
struct edge {
	int v, ne;
}ed[maxn * 2];
int head[maxn], cnt, n;
int fa[maxn], son[maxn], num[maxn], deep[maxn];
int p[maxn], fp[maxn], top[maxn];
int pos;
void init() {
	cnt = 0;
	memset(head, -1, sizeof head);
	pos = 0;
	memset(son, -1, sizeof son);
}
void addedge(int u, int v) {
	ed[cnt].v = v;
	ed[cnt].ne = head[u];
	head[u] = cnt++;
}
void dfs1(int u, int pre, int d) {
	deep[u] = d;
	fa[u] = pre;
	num[u] = 1;
	for (int i = head[u]; ~i; i = ed[i].ne) {
		int v = ed[i].v;
		if (v == pre)continue;
		dfs1(v, u, d + 1);
		num[u] += num[v];
		if (son[u] == -1 || num[v] > num[son[u]])
			son[u] = v;
	}
}
void getpos(int u, int sp) {
	top[u] = sp;
	p[u] = pos++;
	fp[p[u]] = u;
	if (son[u] == -1)return;
	getpos(son[u], sp);
	for (int i = head[u]; ~i; i = ed[i].ne) {
		int v = ed[i].v;
		if (v != son[u] && v != fa[u]) {
			getpos(v, v);
		}
	}
}
struct node {
	int l, r;
	int Max, Min, lazy;
}c[maxn * 4];
void build(int rt, int l, int r) {
	c[rt].l = l; c[rt].r = r;
	c[rt].Max = -0x3f3f3f3f, c[rt].Min = 0x3f3f3f3f, c[rt].lazy = 0;
	if (l == r)return;
	int mid = (l + r) >> 1;
	build(rt << 1, l, mid);
	build((rt << 1) | 1, mid + 1, r);
}
void pushup(int rt) {
	c[rt].Max = max(c[rt << 1].Max, c[(rt << 1) | 1].Max);
	c[rt].Min = min(c[(rt << 1)].Min, c[(rt << 1) | 1].Min);
}
void pushdown(int rt) {
	if (c[rt].lazy) {
		c[rt].lazy = 0;
		//
		c[rt << 1].lazy ^= 1;
		swap(c[rt << 1].Max, c[rt << 1].Min);
		c[rt << 1].Max = -c[rt << 1].Max;	c[rt << 1].Min = -c[rt << 1].Min;
		//
		c[(rt << 1) | 1].lazy ^= 1;
		swap(c[(rt << 1) | 1].Max, c[(rt << 1) | 1].Min);
		c[(rt << 1) | 1].Max = -c[(rt << 1) | 1].Max;	c[(rt << 1) | 1].Min = -c[(rt << 1) | 1].Min;
	}
}
void update(int rt, int k, int val) {
	if (c[rt].l == k&&c[rt].r == k) {
		c[rt].Max = val;
		c[rt].Min = val;
		return;
	}
	pushdown(rt);
	int mid = (c[rt].l + c[rt].r) >> 1;
	if (k <= mid)update(rt << 1, k, val);
	else update(((rt << 1) | 1), k, val);
	pushup(rt);
}
void updates(int rt, int l, int r) {
	if (c[rt].l == l&&c[rt].r == r) {
		swap(c[rt].Max, c[rt].Min);
		c[rt].Max = -c[rt].Max;
		c[rt].Min = -c[rt].Min;
		c[rt].lazy ^= 1;
		return;
	}
	pushdown(rt);
	int mid = (c[rt].l + c[rt].r) >> 1;
	if (r <= mid)updates(rt << 1, l, r);
	else if (l > mid)updates((rt << 1) | 1, l, r);
	else {
		updates(rt << 1, l, mid);
		updates((rt << 1) | 1, mid + 1, r);
	}
	pushup(rt);
}
void see(int rt, int l, int r) {
	//if (l == r)
	//	cout << "L:" << fp[l] << " R:" << fp[r] << " Max:" << c[rt].Max << " Min:" << c[rt].Min << endl;
	if (l == r)return;
	pushdown(rt);
	int mid = (l + r) >> 1;
	see(rt << 1, l, mid);
	see((rt << 1) | 1, mid + 1, r);
	pushup(rt);
}
int query(int rt, int l, int r) {
	if (c[rt].l == l&&c[rt].r == r)
		return c[rt].Max;
	int mid = (c[rt].l + c[rt].r) >> 1, ans;
	pushdown(rt);
	if (r <= mid)ans = query(rt << 1, l, r);
	else if (l > mid)ans = query((rt << 1) | 1, l, r);
	else return ans = max(query(rt << 1, l, mid), query((rt << 1) | 1, mid + 1, r));
	return ans;
}
int find(int u, int v) {
	int f1 = top[u], f2 = top[v];
	int tmp = -0x3f3f3f3f;
	while (f1 != f2) {
		if (deep[f1] < deep[f2]) {
			swap(f1, f2);
			swap(u, v);
		}
		tmp = max(tmp, query(1, p[f1], p[u]));
		u = fa[f1]; f1 = top[u];
	}
	if (u == v)return tmp;
	if (deep[u] > deep[v])swap(u, v);
	return max(tmp, query(1, p[son[u]], p[v]));
}
void Change(int u, int v) {
	int f1 = top[u], f2 = top[v];
	while (f1 != f2) {
		if (deep[f1] < deep[f2]) {
			swap(f1, f2);
			swap(u, v);
		}
		//cout << "Change: " << p[f1] << " "<<p[u] << endl;
		updates(1, p[f1], p[u]);
		u = fa[f1]; f1 = top[u];
	}
	if (u == v)return;
	if (deep[u] > deep[v])swap(u, v);
	//cout << "Change: " << p[son[u]] << " " << p[v] << endl;
	updates(1, p[son[u]], p[v]);
}
int e[maxn][3];
int main() {
	int te, n;
	scanf("%d", &te);
	while (te--) {
		scanf("%d", &n);
		init();
		for (int i = 1; i <= n - 1; i++) {
			scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
			addedge(e[i][0], e[i][1]);
			addedge(e[i][1], e[i][0]);
		}
		dfs1(1, 0, 0);
		getpos(1, 1);
		build(1, 1, n - 1);
		for (int i = 1; i <= n - 1; i++) {
			if (deep[e[i][0]] < deep[e[i][1]]) {
				swap(e[i][0], e[i][1]);
			}
			update(1, p[e[i][0]], e[i][2]);
		}
		char que[10];
		while (scanf("%s", que) != EOF) {
			if (que[0] == 'D')break;
			int a, b;
			scanf("%d%d", &a, &b);
			if (que[0] == 'Q') {
				printf("%d\n", find(a, b));
			}
			else if (que[0] == 'N') {
				Change(a, b);
			}
			else {
				update(1, p[e[a][0]], b);
			}
		}
	}
	return 0;
}