题目：

洛谷4219

分析：

很明显，查询的是删掉某条边后两端点所在连通块大小的乘积。

有加边和删边，想到LCT。但是我不会用LCT查连通块大小啊。 果断弃了

有加边和删边，还跟连通性有关，于是开始yy线段树分治做法（不知道线段树分治？推荐一个 伪模板 题 BZOJ4025二分图 事实上这个链接是指向我的博客的 ）。把每次操作（加边或查询）看做一个时刻，一条边存在的区间就是它加入后没有被查询的时间区间的并。于是用可撤销并查集维护一下连通块大小即可。

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <map>
#include <cassert>
#undef i
#undef j
#undef k
#undef min
#undef max
#undef true
#undef false
#undef swap
#undef sort
#undef if
#undef for
#undef while
#undef printf
#undef scanf
#undef putchar
#undef getchar
#define _ 0
using namespace std;

namespace zyt
{
    template<typename T>
    inline bool read(T &x)
    {
        char c;
        bool f = false;
        x = 0;
        do
            c = getchar();
        while (c != EOF && c != '-' && !isdigit(c));
        if (c == EOF)
            return false;
        if (c == '-')
            f = true, c = getchar();
        do
            x = x * 10 + c - '0', c = getchar();
        while (isdigit(c));
        if (f)
            x = -x;
        return true;
    }
    inline bool read(char &c)
    {
        do
            c = getchar();
        while (c != EOF && !isgraph(c));
        return c != EOF;
    }
    template<typename T>
    inline void write(T x)
    {
        static char buf[20];
        char *pos = buf;
        if (x < 0)
            putchar('-'), x = -x;
        do
            *pos++ = x % 10 + '0';
        while (x /= 10);
        while (pos > buf)
            putchar(*--pos);
    }
    typedef long long ll;
    const int N = 1e5 + 10, B = 17, QUERY = 0, ADD = 1;
    int n, q;
    ll ans[N];
    struct node
    {
        bool type;
        int x, y;
    }arr[N];
    namespace UFS
    {
        int fa[N], rk[N], size[N], top;
        struct node
        {
            int x, y, fax, rky, sizey;
        }stack[N];
        void init(const int n)
        {
            for (int i = 1; i <= n; i++)
                fa[i] = i, rk[i] = size[i] = 1;
        }
        int f(const int u)
        {
            return fa[u] == u ? u : f(fa[u]);
        }
        bool merge(const int u, const int v)
        {
            int x = f(u), y = f(v);
            if (x == y)
                return false;
            if (rk[x] > rk[y])
                swap(x, y);
            stack[top++] = (node){x, y, fa[x], rk[y], size[y]};
            fa[x] = y, size[y] += size[x];
            if (rk[x] == rk[y])
                ++rk[y];
            return true;
        }
        int query(const int u)
        {
            assert(f(u) < N);
            return size[f(u)];
        }
        void undo(const int bck)
        {
            while (top > bck)
            {
                --top;
                int x = stack[top].x, y = stack[top].y;
                assert(x < N && y < N);
                fa[x] = stack[top].fax;
                rk[y] = stack[top].rky;
                size[y] = stack[top].sizey;
            }
        }
    }
    namespace Segment_Tree
    {
        struct edge
        {
            int x, y, next;
        }e[N * (B + 1)];
        int head[1 << (B + 1) | 11], ecnt;
        inline void init()
        {
            memset(head, -1, sizeof(head));
        }
        inline void add(const int a, const int b, const int c)
        {
            e[ecnt] = (edge){b, c, head[a]}, head[a] = ecnt++;
        }
        inline void insert(const int rot, const int lt, const int rt, const int ls, const int rs, const int x, const int y)
        {
            if (ls <= lt && rt <= rs)
            {
                add(rot, x, y);
                return;
            }
            int mid = (lt + rt) >> 1;
            if (ls <= mid)
                insert(rot << 1, lt, mid, ls, rs, x, y);
            if (rs > mid)
                insert(rot << 1 | 1, mid + 1, rt, ls, rs, x, y);
        }
        inline void solve(const int rot, const int lt, const int rt)
        {
            int bck = UFS::top;
            for (int i = head[rot]; ~i; i = e[i].next)
                UFS::merge(e[i].x, e[i].y);
            if (lt == rt)
            {
                if (arr[lt].type == QUERY)
                    ans[lt] = (ll)UFS::query(arr[lt].x) * UFS::query(arr[lt].y);
                UFS::undo(bck);
                return;
            }
            int mid = (lt + rt) >> 1;
            solve(rot << 1, lt, mid);
            solve(rot << 1 | 1, mid + 1, rt);
            UFS::undo(bck);
        }
    }
    map<pair<int, int>, int> lastins;
    int work()
    {
        read(n), read(q);
        UFS::init(n);
        Segment_Tree::init();
        for (int i = 1; i <= q; i++)
        {
            char opt;
            read(opt), read(arr[i].x), read(arr[i].y);
            if (arr[i].x > arr[i].y)
                swap(arr[i].x, arr[i].y);
            arr[i].type = (opt == 'Q' ? QUERY : ADD);
            pair<int, int> p = make_pair(arr[i].x, arr[i].y);
            if (arr[i].type == ADD)
                lastins[p] = i;
            else
            {
                Segment_Tree::insert(1, 1, q, lastins[p], i - 1, p.first, p.second);
                lastins[p] = i + 1;
            }
        }
        for (map<pair<int, int>, int>::iterator it = lastins.begin(); it != lastins.end(); it++)
            if (it->second <= q)
                Segment_Tree::insert(1, 1, q, it->second, q, it->first.first, it->first.second);
        Segment_Tree::solve(1, 1, q);
        for (int i = 1; i <= q; i++)
            if (arr[i].type == QUERY)
                write(ans[i]), putchar('\n');
        return (0^_^0);
    }
}
int main()
{
    return zyt::work();
}