<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", &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); } }
}