很好的题，请注意本题独特的 link（一天的代价）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]
#define fa(p) tr[p].f
struct node{int ch[2],f,s,siz,tag;}tr[N];
bool notrt(int p){return (lc(fa(p))==p)||(rc(fa(p))==p);}
void pushup(int p){tr[p].s=tr[lc(p)].s+tr[rc(p)].s+1+tr[p].siz;}
void pushdown(int p)
{
	if(tr[p].tag)
	{
		swap(lc(p),rc(p));
		tr[lc(p)].tag^=1;tr[rc(p)].tag^=1;
		tr[p].tag=0;
	}
}
void pushall(int x)
{
	if(notrt(x))pushall(fa(x));
	pushdown(x);
}
void rotate(int x)
{
	int y=fa(x),z=fa(y),k=rc(y)==x;
	if(notrt(y))tr[z].ch[rc(z)==y]=x;fa(x)=z;
	tr[y].ch[k]=tr[x].ch[k^1];fa(tr[x].ch[k^1])=y;
	tr[x].ch[k^1]=y;fa(y)=x;
	pushup(y);pushup(x);
}
void splay(int x)
{
	pushall(x);
	while(notrt(x))
	{
		int y=fa(x),z=fa(y);
		if(notrt(y))((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
		rotate(x);
	}
}
void access(int x)
{
	for(int y=0;x;)
	{
		splay(x);
		tr[x].siz+=tr[rc(x)].s-tr[y].s;
		rc(x)=y;
		pushup(x);
		y=x;x=fa(x);
	}
}
void makert(int x)
{
	access(x);
	splay(x);
	tr[x].tag^=1;
}
void split(int x,int y)
{
	makert(x);
	access(y);
	splay(y);
}
int findrt(int x)
{
	access(x);
	splay(x);
	while(lc(x))pushdown(x),x=lc(x);
	splay(x);
	return x;
}
void link(int x,int y)
{
	makert(x);makert(y);
	fa(x)=y,tr[y].siz+=tr[x].s;
}
void cut(int x,int y)
{
	split(x,y);
	fa(x)=lc(y)=0;
	pushup(x);
}
signed main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++)tr[i].s=1,tr[i].siz=0;
	for(int i=1;i<=m;i++)
	{
		string op;cin>>op;int x,y;cin>>x>>y;
		if(op[0]=='Q')
		{
			cut(x,y);
			makert(x);makert(y);
			cout<<tr[x].s*tr[y].s<<'\n';
			link(x,y);
		}
		if(op[0]=='A')
			link(x,y);
	}
	return 0;
}

P4219 [BJOI2014] 大融合

题目分析

给定n个点的无向图，初始无边。有m个操作：操作1为连接u和v，操作2为询问u和v之间的路径数。由于路径数在动态添加边时难以直接计算，采用线段树分治结合可撤销并查集处理。

思路

1. 线段树分治：将所有操作按时间编号，对每个查询操作，确定其对应的时间区间[L, R]（L为查询前最后一次添加边的时间，R为查询时间），分解为O(log m)个线段树节点区间。
2. 可撤销并查集：维护连通性，支持合并与撤销操作，用栈记录每次合并信息，便于回溯。
3. 分治处理：递归处理线段树节点，在区间内执行添加边操作，处理查询，记录路径数，最后撤销添加的边。

代码实现

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, size;
    vector<tuple<int, int, int, int, int, int>> st; // u, v, pu, pv, su, sv

    DSU(int n) : parent(n+1), size(n+1, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int u) { return parent[u] == u ? u : find(parent[u]); }

    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;
        if (size[u] < size[v]) swap(u, v);
        st.emplace_back(u, v, parent[u], parent[v], size[u], size[v]);
        parent[v] = u;
        size[u] += size[v];
    }

    void rollback(int t) {
        while (st.size() > t) {
            auto [u, v, pu, pv, su, sv] = st.back(); st.pop_back();
            parent[u] = pu;
            parent[v] = pv;
            size[u] = su;
            size[v] = sv;
        }
    }
};

struct Query {
    int u, v, idx;
};

struct SegmentNode {
    int l, r;
    vector<pair<int, int>> adds;
    vector<Query> queries;
    SegmentNode *left, *right;
    SegmentNode(int l, int r) : l(l), r(r), left(nullptr), right(nullptr) {}
};

SegmentNode* build(int l, int r, const vector<tuple<int, int, int>>& adds) {
    auto node = new SegmentNode(l, r);
    if (l == r) return node;
    int mid = (l + r) / 2;
    for (auto [t, u, v] : adds) {
        if (t <= mid) node->left->adds.emplace_back(u, v);
        else node->right->adds.emplace_back(u, v);
    }
    node->left = build(l, mid, adds);
    node->right = build(mid+1, r, adds);
    return node;
}

void dfs(SegmentNode* node, DSU& dsu, vector<int>& ans) {
    int t = dsu.st.size();
    for (auto [u, v] : node->adds) dsu.unite(u, v);
    for (auto& q : node->queries) {
        int u = q.u, v = q.v, idx = q.idx;
        if (dsu.find(u) == dsu.find(v)) ans[idx] = dsu.size[dsu.find(u)];
        else ans[idx] = 0;
    }
    if (node->left) dfs(node->left, dsu, ans);
    if (node->right) dfs(node->right, dsu, ans);
    dsu.rollback(t);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> adds; // (t, u, v)
    vector<Query> queries;
    vector<int> ans;
    int t = 0;

    for (int i = 0; i < m; ++i) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 1) adds.emplace_back(++t, u, v);
        else {
            queries.push_back({u, v, ans.size()});
            ans.push_back(0);
        }
    }

    auto root = build(1, t, adds);
    for (auto& q : queries) root->queries.push_back(q);

    DSU dsu(n);
    dfs(root, dsu, ans);
    
    for (int x : ans) cout << x << '\n';
    return 0;
}

注：代码中路径数计算采用连通分量大小，实际应根据题目要求调整，此处为示例。

C136 线段树分治+并查集 P4219 [BJOI2014] 大融合