【题目链接】
点击打开链接【思路要点】
用LinkCutTree维护这棵树，在轻边的父亲处记录子树信息即可。时间复杂度 O(QLogN) O ( Q L o g N ) 。【代码】
#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } struct LinkCutTree { struct Node { int child[2]; int father, up; int size, light; bool rev; } a[MAXN]; int size, n; void init(int x) { n = x; for (int i = 1; i <= n; i++) a[i].size = 1; } void update(int root) { a[root].size = a[root].light + 1; if (a[root].child[0]) a[root].size += a[a[root].child[0]].size; if (a[root].child[1]) a[root].size += a[a[root].child[1]].size; } void pushdown(int root) { if (a[root].rev) { swap(a[root].child[0], a[root].child[1]); if (a[root].child[0]) a[a[root].child[0]].rev ^= true; if (a[root].child[1]) a[a[root].child[1]].rev ^= true; a[root].rev = false; } } bool get(int x) { return a[a[x].father].child[1] == x; } void rotate(int x) { int f = a[x].father, g = a[f].father; a[x].up = a[f].up, a[f].up = 0; pushdown(f), pushdown(x); bool tmp = get(x); a[f].child[tmp] = a[x].child[tmp ^ 1]; if (a[f].child[tmp]) a[a[f].child[tmp]].father = f; a[f].father = x; a[x].child[tmp ^ 1] = f; a[x].father = g; if (g) a[g].child[a[g].child[1] == f] = x; update(f), update(x); } void splay(int x) { pushdown(x); for (int f = a[x].father; (f = a[x].father) != 0; rotate(x)) if (a[f].father) { if (get(x) == get(f)) rotate(f); else rotate(x); } } void access(int x) { splay(x); int tmp = a[x].child[1]; if (tmp != 0) { a[tmp].up = x; a[tmp].father = 0; a[x].child[1] = 0; a[x].light += a[tmp].size; update(x); } while (a[x].up) { int f = a[x].up; splay(f); tmp = a[f].child[1]; if (tmp != 0) { a[tmp].up = f; a[tmp].father = 0; a[f].light += a[tmp].size; } a[f].child[1] = x; a[f].light -= a[x].size; a[x].father = f; a[x].up = 0; update(f); splay(x); } } void link(int x, int y) { access(x); splay(x); reverse(y); access(y); splay(y); a[x].child[1] = y; a[y].father = x; update(x); } void reverse(int x) { access(x); splay(x); a[x].rev ^= true; } long long query(int x, int y) { reverse(x); access(y); splay(x); int tmp = a[x].size; int tnp = a[y].size; return 1ll * (tmp - tnp) * tnp; } } LCT; int main() { int n, m; read(n), read(m); LCT.init(n); for (int i = 1; i <= m; i++) { char opt = getchar(); while (opt != 'A' && opt != 'Q') opt = getchar(); int x, y; read(x), read(y); if (opt == 'A') LCT.link(x, y); else writeln(LCT.query(x, y)); } return 0; }