题解 | 树上行走

题意

n个点的一棵树，每个点是0或1。进入一个点后，所有与它类型不同的点会消失，只能走剩下的边。问进入哪些点能让自己可走的点数最多。

思路

进入一个点后，与它类型不同的点消失，相当于只保留同类型点之间的边。因此问题转化为：在原树中只保留两端类型相同的边，形成若干个连通块。每个连通块内的点可以互相到达。

如果进入某个点，它所在的连通块大小就是可活动点数。为了最大化，我们选择所有最大的连通块中的点。

做法

1. 建图时只加两端类型相同的边。
2. 遍历所有点，BFS/DFS找连通块，记录每个块的大小。
3. 找出所有大小等于最大值的块，把这些块里的点收集起来，排序输出。

代码说明

• g 只存同类型边。
• vis 标记已访问。
• 用 sz 记录当前最大块大小，ans 存放所有最大块的点。
• 最后对 ans 排序输出。

复杂度 O(n)

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
bool vis[maxn];
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<vector<int>> g(n+1);
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        if(a[u]==a[v]){
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    vector<int> ans;
    int sz=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vector<int> tmp;
            vis[i]=1;
            queue<int> q;
            q.push(i);
            tmp.push_back(i);
            while(!q.empty()){
                int u=q.front();q.pop();
                for(int v:g[u]){
                    if(!vis[v]){
                        vis[v]=1;
                        q.push(v);
                        tmp.push_back(v);
                    }
                }
            }
            if(tmp.size()>sz){
                sz=tmp.size();
                ans=move(tmp);
            }
            else if(tmp.size()==sz){
                for(int t:tmp) ans.push_back(t);
            }
        }
    }
    cout<<ans.size()<<"\n";
    sort(ans.begin(),ans.end());
    cout<<ans[0];
    for(int i=1;i<ans.size();i++) cout<<" "<<ans[i];
}