NC208346. 树上行走
描述
牛牛苦练武功绝学——轻功水上漂，最终没有练成，但是他学会了在树上行走的本领。
这天，牛牛落入了敌人的陷阱，身后有巨石追击，面前有n个点，n-1条边连成一张连通图（一棵树），现在牛牛必须立马选择进入这张图中，但是牛牛发现，这张图有两种不同的点，一旦进入一个点，所有与该点不同类型的点都会消失（相连的边也会消失），牛牛只能走到有边相连的点，牛牛想要自己尽量有更多的点可以活动，那么他可以进入哪些点？
输入描述
第一行有一个正整数表示共有
第二行有个数
表示两种类型的点
接下来行每行有两个正整数
表示
和
之间有一条边
输出描述
第一行输出可以进入的点的个数
第二行从小到大输出这些点的编号
示例1
输入:
3 1 1 0 1 2 1 3
输出:
2 1 2
说明:
落到1和2的情况可以有2的移动位置，是最大的
示例2
输入:
4 1 1 0 0 1 2 2 3 3 4
输出:
4 1 2 3 4
说明:
不论落到哪个点，都有2个位置可以移动C++ 解法, 执行用时: 184ms, 内存消耗: 7928K, 提交时间: 2022-02-23 14:04:33
#include<bits/stdc++.h>
using namespace std;
const int Q=2e5+10;
int p[Q],t[Q],dp[Q],zi[Q],n,a,b,m=1,co=0;
int find(int x){ if(p[x]!=x){p[x]=find(p[x]);}return p[x]; }
int main()
{cin>>n;
for(int i=1;i<=n;i++){cin>>t[i];p[i]=i;dp[i]=1;}
for(int i=1;i<n;i++)
{ cin>>a>>b;
int ga=find(a),gb=find(b);
if(ga!=gb&&t[ga]==t[gb]){dp[ga]+=dp[gb];p[gb]=ga;m=max(dp[a],m);}
}
for(int i=1;i<=n;i++){if(m==dp[find(i)]){zi[co++]=i;}}
cout<<co<<endl; sort(zi,zi+co);
for(int i=0;i<co;i++){cout<<zi[i]<<' ';}
}