LCT新姿势：维护子树信息。

不能带修，子树修改就要toptree了...

题意：动态加边，求子树大小。

解：

维护子树信息只要额外维护虚边连的儿子的信息即可。这里把siz的定义变成子树大小。

哪里会修改虚边呢？link和access。把这两个函数改一改就行了。

注意这里link的时候x和y都要make_root，因为修改只能修改根。

1 #include 
      
         2 #include 
       
          3   4 typedef long long LL;  5 const int N = 100010;  6   7 int fa[N], s[N][2], sum[N], val[N], S[N], Sp;  8 bool rev[N];  9  10 inline bool no_root(int x) { 11     return (s[fa[x]][0] == x) || (s[fa[x]][1] == x); 12 } 13  14 inline void pushup(int x) { 15     sum[x] = sum[s[x][0]] + sum[s[x][1]] + val[x]; 16     return; 17 } 18  19 inline void pushdown(int x) { 20    if(rev[x]) { 21         if(s[x][0]) { 22             rev[s[x][0]] ^= 1; 23         } 24         if(s[x][1]) { 25             rev[s[x][1]] ^= 1; 26         } 27         std::swap(s[x][0], s[x][1]); 28         rev[x] = 0; 29    } 30    return; 31 } 32  33 inline void rotate(int x) { 34     int y = fa[x]; 35     int z = fa[y]; 36     bool f = (s[y][1] == x); 37  38     fa[x] = z; 39     if(no_root(y)) { 40         s[z][s[z][1] == y] = x; 41     } 42     s[y][f] = s[x][!f]; 43     if(s[x][!f]) { 44         fa[s[x][!f]] = y; 45     } 46     s[x][!f] = y; 47     fa[y] = x; 48  49     pushup(y); 50     pushup(x); 51     return; 52 } 53  54 inline void splay(int x) { 55     int y = x; 56     S[++Sp] = y; 57     while(no_root(y)) { 58         y = fa[y]; 59         S[++Sp] = y; 60     } 61     while(Sp) { 62         pushdown(S[Sp]); 63         Sp--; 64     } 65  66     y = fa[x]; 67     int z = fa[y]; 68     while(no_root(x)) { 69         if(no_root(y)) { 70             (s[z][1] == y) ^ (s[y][1] == x) ? 71             rotate(x) : rotate(y); 72         } 73         rotate(x); 74         y = fa[x]; 75         z = fa[y]; 76     } 77     return; 78 } 79  80 inline void access(int x) { 81     int y = 0; 82     while(x) { 83         splay(x); 84         val[x] += sum[s[x][1]] - sum[y]; 85         s[x][1] = y; 86         pushup(x); 87         y = x; 88         x = fa[x]; 89     } 90     return; 91 } 92  93 inline void make_root(int x) { 94     access(x); 95     splay(x); 96     rev[x] = 1; 97     return; 98 } 99 100 inline void link(int x, int y) {101     make_root(x);102     make_root(y);103     fa[x] = y;104     val[y] += sum[x];105     sum[y] += sum[x];106     return;107 }108 109 inline int ask(int x, int r) {110     make_root(x);111     access(r);112     splay(r);113     return sum[x];114 }115 116 char str[20];117 118 int main() {119     int n, q;120     scanf("%d%d", &n, &q);121     for(int i = 1; i <= n; i++) {122         val[i] = 1;123     }124     for(int i = 1, x, y; i <= q; i++) {125         scanf("%s%d%d", str, &x, &y);126         if(str[0] == 'A') {127             link(x, y);128         }129         else {130             int t = ask(x, y);131             int tt = ask(y, x);132             printf("%lld\n", 1ll * t * tt);133         }134     }135 136     return 0;137 }