BZOJ2157 旅游

去找水题于是找到这么一道恶心的代码题。其实应该可以用函数指针来优化一下代码量，不过懒得了。虽然复制粘贴导致调试了老半天。

水水的链剖+线段树。然后tag打一打就好了。

最近是装备了高超的开坑技巧啊。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct seg {
	int l, r, s, a, b, rv;
	seg *ls, *rs;
	inline void update() {
		if (l + 1 < r) {
			s = ls-> s + rs-> s;
			a = min(ls-> a, rs-> a);
			b = max(ls-> b, rs-> b);
			if (rv) {
				s = -s;
				swap(a, b);
				a = -a;
				b = -b;
			}
		}
		else
			a = b = s;
	}
	inline void chgTag() {
		s = -s;
		swap(a, b);
		a = -a;
		b = -b;
		rv ^= 1;
	}
	inline void downTag() {
		if (rv) {
			rv = 0;
			if (l + 1 < r) {
				ls-> chgTag();
				rs-> chgTag();
			}
		}
	}
};
struct edge {
	int t, v;
	edge *next;
};

const int maxn = 20009;

int n, m, fa[maxn], d[maxn], vl[maxn], ea[maxn], eb[maxn];
int sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];
seg slst[maxn << 2], *sp(slst), *rt[maxn];

inline void addEdge(int u, int v, int w) {
	ep-> t = v;
	ep-> v = w;
	ep-> next = head[u];
	head[u] = ep ++;
}

#define midp(p) ((p->l+p->r)>>1)
inline seg* sgtBuild(int l, int r) {
	seg* p(sp ++);
	p-> l = l;
	p-> r = r;
	if (l + 1 < r) {
		p-> ls = sgtBuild(l, midp(p));
		p-> rs = sgtBuild(midp(p), r);
	}
	return p;
}
inline void sgtChg(seg* p, int p0, int v0) {
	if (p-> l + 1 == p-> r) {
		p-> rv = 0;
		p-> s = v0;
	}
	else {
		p-> downTag();
		if (p0 < midp(p))
			sgtChg(p-> ls, p0, v0);
		else
			sgtChg(p-> rs, p0, v0);
	}
	p-> update();
}
inline int sgtSum(seg* p, int l, int r) {
	if (p-> l == l && p-> r == r)
		return p-> s;
	else {
	   p-> downTag();
	   if (r <= midp(p))
		   return sgtSum(p-> ls, l, r);
	   else if (l >= midp(p))
		   return sgtSum(p-> rs, l, r);
	   else
		   return sgtSum(p-> ls, l, midp(p)) + sgtSum(p-> rs, midp(p), r);
	}
}
inline int sgtMin(seg* p, int l, int r) {
	if (p-> l == l && p-> r == r)
		return p-> a;
	else {
		p-> downTag();
		if (r <= midp(p))
			return sgtMin(p-> ls, l, r);
		else if (l >= midp(p))
			return sgtMin(p-> rs, l, r);
		else
			return min(sgtMin(p-> ls, l, midp(p)), sgtMin(p-> rs, midp(p), r));
	}
}
inline int sgtMax(seg* p, int l, int r) {
	if (p-> l == l && p-> r == r)
		return p-> b;
	else {
		p-> downTag();
		if (r <= midp(p))
			return sgtMax(p-> ls, l, r);
		else if (l >= midp(p))
			return sgtMax(p-> rs, l, r);
		else
			return max(sgtMax(p-> ls, l, midp(p)), sgtMax(p-> rs, midp(p), r));
	}
}
inline void sgtRev(seg* p, int l, int r) {
	if (p-> l == l && p-> r == r)
		p-> chgTag();
	else {
		p-> downTag();
		if (r <= midp(p))
			sgtRev(p-> ls, l, r);
		else if (l >= midp(p))
			sgtRev(p-> rs, l, r);
		else
			sgtRev(p-> ls, l, midp(p)), sgtRev(p-> rs, midp(p), r);
	}
	p-> update();
}

#define cpos(_p_) (d[_p_]-d[ch[fc[_p_]]])

void divide() {
	static int q[maxn];
	int hd(0), tl(1);
	q[0] = 0;
	memset(d, 0, sizeof(d));
	d[0] = 1;
	fa[0] = 0;
	vl[0] = 0;
	while (hd < tl) {
		int p(q[hd ++]);
		for (edge* e = head[p]; e; e = e-> next)
			if (!d[e-> t]) {
				fa[e-> t] = p;
				d[e-> t] = d[p] + 1;
				q[tl ++] = e-> t;
				vl[e-> t] = e-> v;
			}
	}
	tc = 0;
	for (int ti = tl - 1; ti >= 0; -- ti) {
		int p(q[ti]), z(-1);
		sz[p] = 1;
		for (edge* e = head[p]; e; e = e-> next)
			if (e-> t != fa[p]) {
				sz[p] += sz[e-> t];
				if (z == -1 || sz[e-> t] > sz[z])
					z = e-> t;
			}
		if (z == -1)
			cl[fc[p] = ++ tc] = 1;
		else
			++ cl[fc[p] = fc[z]];
		ch[fc[p]] = p;
	}
	for (int i = 1; i <= tc; ++ i)
		rt[i] = sgtBuild(0, cl[i]);
	for (int i = 0; i < n; ++ i)
		sgtChg(rt[fc[i]], cpos(i), vl[i]);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d", &n);
	memset(head, 0, sizeof(d));
	for (int i = 1; i < n; ++ i) {
		int w;
		scanf("%d%d%d", ea + i, eb + i, &w);
		addEdge(ea[i], eb[i], w);
		addEdge(eb[i], ea[i], w);
	}
	divide();
	scanf("%d", &m);
	while (m --) {
		char opt[7];
		int u, v, w;
		scanf("%s", opt);
		if (opt[0] == 'C') {
			scanf("%d%d", &u, &w);
			if (d[ea[u]] > d[eb[u]])
				swap(ea[u], eb[u]);
			v = eb[u];
			sgtChg(rt[fc[v]], cpos(v), w);
		}
		else if (opt[0] == 'N') {
			scanf("%d%d", &u, &v);
			while (fc[u] ^ fc[v])
				if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
					sgtRev(rt[fc[u]], 0, cpos(u) + 1);
					u = fa[ch[fc[u]]];
				}
				else {
					sgtRev(rt[fc[v]], 0, cpos(v) + 1);
					v = fa[ch[fc[v]]];
				}
			if (d[u] > d[v])
				swap(u, v);
			if (u ^ v)
				sgtRev(rt[fc[u]], cpos(u) + 1, cpos(v) + 1);
		}
		else if (opt[0] == 'S') {
			int s(0);
			scanf("%d%d", &u, &v);
			while (fc[u] ^ fc[v])
				if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
					s += sgtSum(rt[fc[u]], 0, cpos(u) + 1);
					u = fa[ch[fc[u]]];
				}
				else {
					s += sgtSum(rt[fc[v]], 0, cpos(v) + 1);
					v = fa[ch[fc[v]]];
				}
			if (d[u] > d[v])
				swap(u, v);
			if (u ^ v)
				s += sgtSum(rt[fc[u]], cpos(u) + 1, cpos(v) + 1);
			printf("%d\n", s);
		}
		else if (opt[1] == 'I') {
			int s(0x3f3f3f3f);
			scanf("%d%d", &u, &v);
			while (fc[u] ^ fc[v])
				if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
					s = min(s, sgtMin(rt[fc[u]], 0, cpos(u) + 1));
					u = fa[ch[fc[u]]];
				}
				else {
					s = min(s, sgtMin(rt[fc[v]], 0, cpos(v) + 1));
					v = fa[ch[fc[v]]];
				}
			if (d[u] > d[v])
				swap(u, v);
			if (u ^ v)
				s = min(s, sgtMin(rt[fc[u]], cpos(u) + 1, cpos(v) + 1));
			printf("%d\n", s);
		}
		else if (opt[1] == 'A') {
			int s(-0x3f3f3f3f);
			scanf("%d%d", &u, &v);
			while (fc[u] ^ fc[v])
				if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
					s = max(s, sgtMax(rt[fc[u]], 0, cpos(u) + 1));
					u = fa[ch[fc[u]]];
				}
				else {
					s = max(s, sgtMax(rt[fc[v]], 0, cpos(v) + 1));
					v = fa[ch[fc[v]]];
				}
			if (d[u] > d[v])
				swap(u, v);
			if (u ^ v)
				s = max(s, sgtMax(rt[fc[u]], cpos(u) + 1, cpos(v) + 1));
			printf("%d\n", s);
		}
	}
}