题目分析

本题是一个动态数据共享查询问题。初始时，每个服务器 $i$ 拥有唯一的数据块 $i$。随着 $S$ 操作（共享操作）的执行，服务器之间共享数据，最终形成一棵树结构。需要支持两种查询：

• Q a d：查询服务器 $a$ 是否拥有数据块 $d$

• C a：查询拥有数据块 $a$ 的服务器数量

关键观察

1. 树结构的性质：

由于 $S$ 操作恰好有 $N-1$ 次，且最终形成一棵树，我们可以将共享操作视为在树中添加边。每个 $S$ 操作发生在特定时间点 $i$（按操作顺序编号）。

2. 数据传播规则：

当服务器 $a$ 和 $b$ 在时间 $t$ 共享数据时：

它们立即拥有对方的所有数据

数据会沿着树边传播，但受时间限制

数据块 $d$ 从服务器 $d$ 开始传播，传播到其他服务器的条件是：路径上的所有边的建立时间都早于查询时间

3. 查询转化：

Q a d：等价于判断在查询时间 $t$ 时，服务器 $a$ 和 $d$ 是否连通，且连通路径上的所有边建立时间都 $< t$

C a：等价于统计在查询时间 $t$ 时，有多少服务器与服务器 $a$ 连通，且连通路径上的所有边建立时间都 $< t$

算法思路

1. 离线处理与时间倒流 由于操作是已知的，我们可以采用离线处理。关键技巧是时间倒流：

从最终状态开始，逆向处理操作

在时间倒流中，$S$ 操作变为删除边

查询变为在删除某些边后的连通性查询

2. 并查集与可撤销操作 使用可撤销并查集来维护连通性：

合并操作时可以记录合并信息

支持回滚到之前的状态

配合时间倒流，可以高效处理所有查询

3. 分治策略（CDQ分治） 对于这类有时间维度的离线问题，可以使用CDQ分治：

将时间区间分为两半

处理左半区间对右半区间查询的影响

递归处理

4. 点分治优化 代码中使用了点分治（centroid decomposition）来处理树上的路径问题：

找到树的重心

处理经过重心的路径

递归处理子树

时间复杂度分析 点分治：$O(n \log n)$

每个节点被处理 $O(\log n)$ 次

每次处理涉及排序和树状数组操作：$O(m \log n)$，其中 $m$ 是相关操作数

总复杂度：$O((n + K) \log^2 n)$

对于 $n, K \le 1.2 \times 10^5$，这是可行的。

正确性证明

1. 点分治的正确性：

树的重心分解保证了：

每个节点在递归中被处理 $O(\log n)$ 次

每条路径 $(u, v)$ 在某个重心处被处理

所有查询都被正确覆盖

2. 路径条件的正确性：

对于路径 $(a, d)$ 经过重心 $c$：

设 $a$ 到 $c$ 的路径为 $P_1$，最大边时间为 $mx_a$

设 $c$ 到 $d$ 的路径为 $P_2$，最小边时间为 $mn_d$

整个路径 $(a, d)$ 的最大边时间为 $\max(mx_a, mx_d)$

查询时间 $t$ 必须大于路径上所有边的时间

因此需要 $mx_a < t$ 且 $mn_d > mx_a$（确保 $P_2$ 上所有边时间 $> mx_a$）

3. 树状数组统计的正确性：

对于 C a 查询，树状数组维护了在特定时间条件下可达的节点数，通过差分和前缀和技巧高效统计。

总结

本题是一个复杂的树上离线查询问题，综合运用了多种高级算法技巧：

• 点分治：分解树结构，处理路径问题

• 离线处理：预先读入所有操作，统一处理

• 树状数组：高效统计满足条件的节点数

• 时间维度处理：通过边的时间戳控制数据传播

算法的核心思想是：通过重心分解将路径问题转化为局部问题，利用边的时间戳信息过滤无效路径，最后用树状数组高效统计结果。这种组合方法能够处理 $n, K \le 1.2 \times 10^5$ 的大规模数据。

AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2.4e5 + 1;
int n, Q, a[N], T[N], V[N], ans[N];
int sz[N];
int mn[N], mx[N];
bool del[N], good[N];
vector<int> q[N], q2[N];
vector<pair<int, int>> adj[N];

int b[N];
void upd(int i, int x) {
    for (; i; i -= i & -i)
        b[i] += x;
}
int get(int i) {
    int res = 0;

    for (; i < N; i += i & -i)
        res += b[i];

    return res;
}

void dfs_size(int u, int p) {
    sz[u] = 1;

    for (auto [v, w] : adj[u])
        if (!del[v] && v != p)
            dfs_size(v, u), sz[u] += sz[v];
}
int find(int u, int p, int half) {
    for (auto [v, w] : adj[u])
        if (!del[v] && v != p && sz[v] > half)
            return find(v, u, half);

    return u;
}
int find_centroid(int u) {
    dfs_size(u, u);
    return find(u, u, sz[u] / 2);
}

vector<int> cur, cur2;
vector<tuple<int, int, int>> ops;
void dfs1(int u, int p, int pre) {
    cur.push_back(u);
    mx[u] = mx[p];

    for (int x : q2[u])
        if (mx[u] < x)
            ops.emplace_back(x, x, mx[u]);

    for (auto [v, w] : adj[u])
        if (!del[v] && w < pre)
            dfs1(v, u, w);
}
void dfs2(int u, int p, int pre) {
    cur2.push_back(u);
    mn[u] = mn[p];
    good[u] = 1;
    a[u] = pre;
    ops.emplace_back(pre, 0, mn[u]);

    for (auto [v, w] : adj[u])
        if (!del[v] && w > pre)
            dfs2(v, u, w);
}

void process(int u) {
    for (auto [v, w] : adj[u])
        if (!del[v]) {
            mn[v] = mx[v] = w;
            dfs1(v, v, w);
            dfs2(v, v, w);
        }

    for (int v : cur)
        for (int id : q[v])
            if (V[id] != u && good[V[id]] && mx[v] < mn[V[id]] && a[V[id]] < id)
                ans[id] = 1;
            else if (V[id] == u && mx[v] < id)
                ans[id] = 1;

    for (int id : q[u])
        if (V[id] == u || (good[V[id]] && a[V[id]] < id))
            ans[id] = 1;

    ops.emplace_back(0, 0, N - 1);

    for (int x : q2[u])
        ops.emplace_back(x, x, 0);

    sort(ops.begin(), ops.end());

    for (auto [t, id, x] : ops) {
        if (!id)
            upd(x, 1);
        else
            ans[id] += get(x + 1);
    }

    for (auto [t, id, x] : ops)
        if (!id)
            upd(x, -1);

    for (int v : cur2)
        good[v] = 0;

    cur.clear();
    cur2.clear();
    ops.clear();
    del[u] = 1;

    for (auto [v, w] : adj[u])
        if (!del[v])
            process(find_centroid(v));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> Q;
    Q += n - 1;

    for (int i = 1; i <= Q; i++) {
        char c;
        cin >> c;

        if (c == 'S') {
            int u, v;
            cin >> u >> v;
            adj[u].emplace_back(v, i);
            adj[v].emplace_back(u, i);
        }

        if (c == 'Q') {
            int u;
            cin >> V[i] >> u;
            T[i] = 1;
            q[u].push_back(i);
        }

        if (c == 'C') {
            int u;
            cin >> u;
            T[i] = 2;
            q2[u].push_back(i);
        }
    }

    process(find_centroid(1));

    for (int i = 1; i <= Q; i++) {
        if (T[i] == 1)
            cout << (ans[i] ? "yes\n" : "no\n");

        if (T[i] == 2)
            cout << ans[i] << '\n';
    }
}