题解 | #树上行走#

问题分析

本题的核心在于理解“节点消失”引发的动态图收敛过程。根据题目规则：一旦选定进入某点 ，所有与 类型不同的点（即 的点 ）及其关联边均会立即从图中移除。

这意味着：

1. 可达性限制：牛牛只能在与起始点 类型完全相同的点所构成的连通分量中移动。
2. 图的演变：原始树结构 会被简化为若干个互不相连的子图。具体而言，只有当边 满足 时，这条边在进入该区域后才会保留。
3. 目标转化：题目要求找到使得“可移动点数最多”的起始点。这等价于在由相同类型节点组成的连通块中，寻找节点数最多的块，并输出该块（或多个最大块）内的所有节点编号。

算法：属性约束下的森林分解

该问题可以通过图的连通分量分解（Connected Components Decomposition）算法解决。由于原始结构是一棵树，移除部分节点和边后，剩余结构将演变为一个森林（Forest）。

1. 算法选择

为了高效识别同属性连通分量，有两种主流方案：

• 并查集 (Disjoint Set Union, DSU)：由于节点类型和边是静态确定的，可以通过 DSU 维护同类型节点间的连通性。该方案在处理大规模离散合并时非常稳健。
• 广度/深度优先遍历 (BFS/DFS)：通过遍历算法识别每个单纯由同类节点构成的连通区域。

2. 算法应用

1. 将满足 的所有边视为“有效边”，不满足条件的边视为“阻断边”。
2. 利用有效边构建子图。
3. 统计每个连通块的大小。
4. 全局扫描，定位具有最大 的连通块所包含的所有节点。

复杂度分析

• 时间复杂度： 或
  • 如果使用并查集：遍历 条边进行 union 操作，复杂度为 ，其中 是反阿克曼函数，近乎常数。
  • 如果使用 DFS/BFS：访问每个点和每条边各一次，复杂度为 ，即 。
  • 排序结果：最终需要输出有序编号，若按编号由小到大遍历判定，则无需显式排序，复杂度保持在线性范围。
• 空间复杂度：
  • 需要存储邻接表或并查集数组、节点类型数组、以及每个连通块的大小计数。存储空间与 成线性关系。

代码实现

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

struct DSU {
    vector<int> parent;
    vector<int> size;
    int n;

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

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

    void unite(int u, int v) {
        int ru = find(u);
        int rv = find(v);
        if (ru != rv) {
            parent[rv] = ru;
            size[ru] += size[rv];
            size[rv] = 0;
        }
    }

    int getMaxSize() {
        return *max_element(size.begin(), size.end());
    }
};

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

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    DSU dsu(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        if (a[u] == a[v]) {
            dsu.unite(u, v);
        }
    }

    int maxSz = dsu.getMaxSize();
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (dsu.size[dsu.find(i)] == maxSz) {
            ans.push_back(i);
        }
    }
    cout << ans.size() << endl;
    for (int x : ans) {
        cout << x << " ";
    }
    cout << endl;
}