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

 

水水的链剖+线段树。然后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", &amp;n);
memset(head, 0, sizeof(d));
for (int i = 1; i &lt; n; ++ i) {
	int w;
	scanf("%d%d%d", ea + i, eb + i, &amp;w);
	addEdge(ea[i], eb[i], w);
	addEdge(eb[i], ea[i], w);
}
divide();
scanf("%d", &amp;m);
while (m --) {
	char opt[7];
	int u, v, w;
	scanf("%s", opt);
	if (opt[0] == 'C') {
		scanf("%d%d", &amp;u, &amp;w);
		if (d[ea[u]] &gt; 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", &amp;u, &amp;v);
		while (fc[u] ^ fc[v])
			if (d[ch[fc[u]]] &gt; 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] &gt; 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", &amp;u, &amp;v);
		while (fc[u] ^ fc[v])
			if (d[ch[fc[u]]] &gt; 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] &gt; 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", &amp;u, &amp;v);
		while (fc[u] ^ fc[v])
			if (d[ch[fc[u]]] &gt; 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] &gt; 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", &amp;u, &amp;v);
		while (fc[u] ^ fc[v])
			if (d[ch[fc[u]]] &gt; 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] &gt; 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);
	}
}

}