去找水题于是找到这么一道恶心的代码题。其实应该可以用函数指针来优化一下代码量，不过懒得了。虽然复制粘贴导致调试了老半天。
水水的链剖+线段树。然后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);
}
}
}
