题目分析

有 $N$ 个节点，初始时都是孤立的。需要支持两种操作：

• 连接两个不连通的节点（保证形成树结构）
• 查询某条边的负载（经过该边的简单路径数量）

关键观察：对于连接节点 $u$ 和 $v$ 的边，其负载等于删除该边后两个连通分量大小的乘积。

解题思路

核心思想

使用DFS序 + 平衡树 + 并查集的组合方法：

1. 预处理：建立完整树结构，计算DFS序和子树大小
2. 动态维护：用平衡树维护每个连通分量的DFS序集合
3. 查询计算：通过平衡树分裂操作计算边两侧的节点数量

关键技术

• DFS序性质：子树节点在DFS序中连续
• 平衡树合并：FHQ Treap支持高效的分裂与合并
• 并查集：维护连通分量关系

算法步骤

1. 读入所有操作，建立完整的树结构
2. DFS预处理：计算每个节点的DFS序和子树大小
3. 处理操作：
   • 连接操作：合并两个连通分量的平衡树
   • 查询操作：通过平衡树分裂计算边负载

完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
mt19937 rnd(20100107);
int dfn[N], siz[N], tot;
struct edge {
    int v, nxt;
} es[N * 2];
int head[N], gcnt;
void add_edge(int u, int v) {
    es[++gcnt] = {v, head[u]}, head[u] = gcnt;
}
void dfs(int u, int fa) {
    dfn[u] = ++tot;
    siz[u] = 1;

    for (int i = head[u]; i; i = es[i].nxt) {
        int v = es[i].v;

        if (v == fa)
            continue;

        dfs(v, u);
        siz[u] += siz[v];
    }
}
class DSU {
public:
    int pre[N];
    void clear() {
        for (int i = 1; i < N; i++)
            pre[i] = i;
    }
    DSU() {
        clear();
    }
    int findd(int x) {
        return pre[x] = pre[x] == x ? x : findd(pre[x]);
    }
};
DSU P;
class FHQ {
public:
    struct node {
        int ls, rs;
        int sz, dfn;
        unsigned pri;
    } tr[N];
private:
    void push_up(int p) {
        tr[p].sz = tr[tr[p].ls].sz + tr[tr[p].rs].sz + 1;
    }
    void split(int p, int &pl, int &pr, int x) { //按 dfn 分裂
        if (!p) {
            pl = pr = 0;
            return ;
        }

        if (tr[p].dfn <= x) {
            pl = p;
            split(tr[p].rs, tr[p].rs, pr, x);
        } else {
            pr = p;
            split(tr[p].ls, pl, tr[p].ls, x);
        }

        push_up(p);
    }
    int merge(int pl, int pr) {
        if (!pl || !pr)
            return pl | pr;

        if (tr[pl].pri < tr[pr].pri) {
            tr[pl].rs = merge(tr[pl].rs, pr);
            push_up(pl);
            return pl;
        } else {
            tr[pr].ls = merge(pl, tr[pr].ls);
            push_up(pr);
            return pr;
        }
    }
    void print_tree(int p, bool b = 1) {
        if (b)
            cerr << "PRINTING:\n";

        if (!p)
            return ;

        print_tree(tr[p].ls, 0);
        cerr << p << " " << tr[p].dfn << endl;
        print_tree(tr[p].rs, 0);
    }
public:
    int rt[N];
    FHQ() { //本题性质特殊，无需动态分配内存
        for (int i = 1; i < N; i++) {
            tr[i].ls = tr[i].rs = 0;
            tr[i].sz = 1;
            tr[i].dfn = i;
            tr[i].pri = rnd();
            rt[i] = i;
        }
    }
    void add(int u, int v) { //给外界调用的加边
        u = dfn[u], v = dfn[v];
        int x = P.findd(u), y = P.findd(v);

        if (u > v)
            u ^= v ^= u ^= v, x ^= y ^= x ^= y;

        int pl, pr;
        split(rt[x], pl, pr, v - 1);
        rt[x] = merge(merge(pl, rt[y]), pr);
        P.pre[y] = x;
    }
    ll query(int u, int v) {
        int sz = min(siz[u], siz[v]);
        u = dfn[u], v = dfn[v];
        int x = P.findd(u);

        if (u > v)
            u ^= v ^= u ^= v;

        int pl, pm, pr;
        split(rt[x], pl, pm, v - 1);
        split(pm, pm, pr, v + sz - 1);
        ll ans = 1ll * (tr[pl].sz + tr[pr].sz) * tr[pm].sz;
        rt[x] = merge(pl, merge(pm, pr));
        return ans;
    }
};
FHQ T;
struct q_r_y {
    int op, x, y;
} qs[N];
int n, q;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;

    for (int i = 1; i <= q; i++) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        qs[i] = {op == 'A', x, y};

        if (op == 'A') {
            add_edge(x, y);
            add_edge(y, x);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            dfs(i, 0);
    }

    for (int i = 1; i <= q; i++) {
        if (qs[i].op) {
            T.add(qs[i].x, qs[i].y);
        } else {
            printf("%lld\n", T.query(qs[i].x, qs[i].y));
        }
    }

    return 0;
}

代码说明

关键数据结构

• DSU：并查集，维护连通分量关系
• FHQ：无旋Treap，维护每个连通分量的DFS序集合
• dfn[i]：节点i的DFS序
• siz[i]：以节点i为根的子树大小

算法核心

1. 负载计算原理：

   边(u,v)的负载 = size[u侧] × size[v侧]
   

   其中u侧和v侧是删除边(u,v)后分成的两个连通分量。

2. 平衡树维护：

   • 每个连通分量用一个Treap维护其所有节点的DFS序
   • 合并操作：将两个Treap合并
   • 查询操作：通过分裂Treap计算两侧节点数量

3. DFS序利用：

   • 子树节点在DFS序中连续
   • 通过DFS序范围可以快速确定子树节点

关键函数

• add(u, v)：连接两个节点，合并对应的Treap
• query(u, v)：

  // 分裂出三个部分：
  // pl: [min_df, v-1] 区间
  // pm: [v, v+sz-1] 区间（较小子树）
  // pr: [v+sz, max_df] 区间
  // 负载 = (pl.sz + pr.sz) × pm.sz
  

复杂度分析

• 预处理：$O(N)$ DFS遍历
• 每次操作：$O(\log N)$ Treap操作
• 总复杂度：$O(N + Q\log N)$