poj 3237 tree 树链剖分（边权）

将所有的边权变为边上两点里面的深度更大的节点的点权，然后在更新的时候，最后的一条链如果是一个点的话就不更新，反之，从头节点的儿子开始更新，即不更新头节点

Code：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
const ll MAXN = 10005;
struct edge
{
	int to;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot;
int n, m, q;
int fa[MAXN], son[MAXN], deep[MAXN], num[MAXN];
int top[MAXN], p[MAXN], fp[MAXN];
int pos;
int ql, qr;
ll val;
void init()
{
	tot = 0;
	memset(head, -1, sizeof(head));
	pos = 1;
	memset(son, -1, sizeof(son));
}
void add(int a, int b)
{
	e[tot] = edge{ b,head[a] };
	head[a] = tot++;
}
void dfs1(int u, int pre, int dep)
{
	deep[u] = dep;
	fa[u] = pre;
	num[u] = 1;
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		if (v != pre)
		{
			dfs1(v, u, dep + 1);
			num[u] += num[v];
			if (son[u] == -1 || num[son[u]] < num[v])
				son[u] = v;
		}
	}
}
void dfs2(int u, int sp)
{
	top[u] = sp;
	p[u] = pos++;
	fp[p[u]] = u;
	if (son[u] == -1)
		return;
	dfs2(son[u], sp);
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		if (v != son[u] && v != fa[u])
			dfs2(v, v);
	}
}

struct node
{
	int l;
	int r;
	ll minn;
	ll maxn;
	int mark;
}que[MAXN * 4];
void up(int k)
{
	que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
	que[k].minn = min(que[k << 1].minn, que[k << 1 | 1].minn);
}
void down(int k)
{
	if (que[k].mark)
	{
		swap(que[k << 1].maxn, que[k << 1].minn);
		que[k << 1].maxn = -que[k << 1].maxn;
		que[k << 1].minn = -que[k << 1].minn;
		que[k << 1].mark ^= 1;
		swap(que[k << 1 | 1].maxn, que[k << 1 | 1].minn);
		que[k << 1 | 1].maxn = -que[k << 1 | 1].maxn;
		que[k << 1 | 1].minn = -que[k << 1 | 1].minn;
		que[k << 1 | 1].mark ^= 1;
		que[k].mark = 0;
	}
}
void build(int left = 1, int right = pos, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	que[k].maxn = -1e9;
	que[k].minn = 1e9;
	if (left == right)
		return;
	imid;
	build(lson);
	build(rson);
}
void update1(int left = 1, int right = pos, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark = 0;
		que[k].maxn = val;
		que[k].minn = val;
		return;
	}
	down(k);
	imid;
	update1(lson);
	update1(rson);
	up(k);
}
void update2(int left = 1, int right = pos, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		swap(que[k].maxn, que[k].minn);
		que[k].maxn = -que[k].maxn;
		que[k].minn = -que[k].minn;
		que[k].mark ^= 1;
		return;
	}
	down(k);
	imid;
	update2(lson);
	update2(rson);
	up(k);
}
ll query(int left = 1, int right = pos, int k = 1)
{
	if (qr < left || right < ql)
		return -1e9;
	if (ql <= left && right <= qr)
		return que[k].maxn;
	down(k);
	imid;
	return max(query(lson), query(rson));
}

void change2(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);
		}
		ql = p[f1];
		qr = p[u];
		update2();

		u = fa[f1];
		f1 = top[u];
	}
	if (u == v)
		return;
	if (deep[u] > deep[v])
		swap(u, v);
	ql = p[son[u]];
	qr = p[v];
	update2();
}
ll changes(int u, int v)
{
	ll res = -1e9;
	int f1 = top[u], f2 = top[v];
	while (f1 != f2)
	{
		if (deep[f1] < deep[f2])
		{
			swap(f1, f2);
			swap(u, v);
		}
		ql = p[f1];
		qr = p[u];
		res = max(res, query());
		u = fa[f1];
		f1 = top[u];
	}
	if (u == v)
		return res;
	if (deep[u] > deep[v])
		swap(u, v);
	ql = p[son[u]];
	qr = p[v];
	res = max(res, query());
	return res;
}

char op[10];
int in[MAXN][3];
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		init();
		for (int i = 0; i < n - 1; i++)
		{
			scanf("%d%d%d", &in[i][0], &in[i][1], &in[i][2]);
			add(in[i][0], in[i][1]);
			add(in[i][1], in[i][0]);
		}
		dfs1(1, 0, 0);
		dfs2(1, 1);
		build();
		for (int i = 0; i < n - 1; i++)
		{
			if (deep[in[i][0]] > deep[in[i][1]])
				swap(in[i][0], in[i][1]);
			ql = p[in[i][1]];
			qr = ql;
			val = in[i][2];
			update1();
		}
		while (true)
		{
			scanf("%s", op);
			if (op[0] == 'C')
			{
				scanf("%d%lld", &ql, &val);
				ql = p[in[ql - 1][1]];
				qr = ql;
				update1();
			}
			else if (op[0] == 'N')
			{
				scanf("%d%d", &ql, &qr);
				change2(ql, qr);
			}
			else if (op[0] == 'Q')
			{
				scanf("%d%d", &ql, &qr);
				ll res = changes(ql, qr);
				printf("%lld\n", res);
			}
			else
				break;
		}
	}
}