……而且是目前最优解。

先用树剖做法的思路把问题转化成链加单点查，然后不用树剖维护。

我们知道，树上差分可以把链加单点查转化为单点加子树查。

BIT 维护树上差分数组的 DFS 序列即可。

写个 $O(n)$ 建树，再卡卡常，就最优解了。

#include <cstdio>
#include <algorithm>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline void R(int &r)
{
    r = 0;
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
        r = r * 10 + c - '0', c = getchar();
}
inline void C(char &r)
{
    r = getchar();
    while (r < 'A' || r > 'Z')
        r = getchar();
}
void P(long long x)
{
    if (x >= 10)
        P(x / 10);
    *O++ = x % 10 + '0';
}
struct E
{
    int v, t;
} e[200001];
struct S
{
    char o;
    int x, y;
} q[100001];
int n, m, c, p, a[100001], b[100001], d[100001], f[100001], s[100001], t[100001], h[100001];
inline void A(int u, int v)
{
    e[++c] = {v, h[u]};
    h[u] = c;
}
int F(int x) { return x == f[x] ? x : f[x] = F(f[x]); }
inline void M(int x, int k)
{
    for (x = b[x]; x <= n; x += x & -x)
        t[x] += k;
}
inline int Q(int u)
{
    int q = 0, x = b[u] - 1, y = b[u] + s[u] - 1;
    for (; y > x; y &= y - 1)
        q += t[y];
    for (; x > y; x &= x - 1)
        q -= t[x];
    return q;
}
void D(int u)
{
    s[u] = 1;
    a[b[u] = ++p] = 1;
    for (int i = h[u], v; i; i = e[i].t)
        if (!b[v = e[i].v])
            --a[b[u]], d[v] = u, D(v), s[u] += s[v];
}
int main()
{
    R(n);
    R(m);
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    for (int i = 0, x, y; i < m; ++i)
    {
        C(q[i].o);
        R(q[i].x);
        R(q[i].y);
        x = q[i].x;
        y = q[i].y;
        if (q[i].o == 'A')
            A(x, y), A(y, x);
    }
    for (int i = 1; i <= n; ++i)
        if (!b[i])
            D(i);
    for (int i = 1; i <= n; ++i)
        a[i] += a[i - 1], t[i] = a[i] - a[i & i - 1];
    for (int i = 0, g, x, y, X; i < m; ++i)
    {
        if (d[x = q[i].x] == (y = q[i].y))
            swap(x, y);
        X = F(x);
        g = Q(y);
        if (q[i].o == 'A')
        {
            M(x, g);
            if (d[X])
                M(d[X], -g);
            f[F(y)] = F(x);
        }
        else
            P(1ll * g * (Q(X) - g)), *O++ = '\n';
    }
    return fwrite(obuf, O - obuf, 1, stdout), 0;
}