树上行走【牛客tracker 每日一题】

树上行走时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述牛牛苦练武功绝学——轻功水上漂最终没有练成但是他学会了在树上行走的本领。这天牛牛落入了敌人的陷阱身后有巨石追击面前有n nn个点n − 1 n-1n−1条边连成一张连通图一棵树现在牛牛必须立马选择进入这张图中但是牛牛发现这张图有两种不同的点一旦进入一个点所有与该点不同类型的点都会消失相连的边也会消失牛牛只能走到有边相连的点牛牛想要自己尽量有更多的点可以活动那么他可以进入哪些点输入描述第一行有一个正整数n nn表示共有n nn个点n ≤ 2 × 10 5 n≤2×10^5n≤2×105第二行有n nn个数a i a_iai​表示两种类型的点0 ≤ a i ≤ 1 0≤a_i≤10≤ai​≤1接下来n − 1 n−1n−1行每行有两个正整数u v u v ≤ n uvuv≤nuvuv≤n表示u uu和v vv之间有一条边输出描述第一行输出可以进入的点的个数第二行从小到大输出这些点的编号示例1输入3 1 1 0 1 2 1 3输出2 1 2说明落到1 11和2 22的情况可以有2 22的移动位置是最大的示例2输入4 1 1 0 0 1 2 2 3 3 4输出4 1 2 3 4说明不论落到哪个点都有2 22个位置可以移动解题思路本题核心是并查集求解同类型节点的最大连通块题目要求进入节点后仅保留同类型节点因此只需统计树上类型相同的节点构成的连通块大小。初始化并查集遍历树的所有边仅将类型一致的相邻节点合并统计每个连通块的节点数量找到最大连通块的尺寸。所有隶属于最大连通块的节点就是能让牛牛获得最大活动范围的可选节点。最后统计这些节点的数量并按从小到大的顺序输出。并查集的路径压缩优化让操作均摊时间复杂度接近O ( 1 ) O(1)O(1)完美适配n ≤ 2 × 10 5 n \le 2 \times 10^5n≤2×105的大规模数据要求。总结核心逻辑保留同类型节点用并查集维护连通块选择最大连通块内的所有节点。关键操作遍历树边合并同类节点统计连通块大小筛选出最大连通块的节点。效率保障并查集路径压缩优化线性遍历处理数据高效满足大数据量的时间限制。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N2e610;constll p1e97;constll INF1e18;constll M5e310;ll py[N],ne[N],cnt[N],ans[N];ll mx,num;llfind(ll x){returnpy[x]x?x:py[x]find(py[x]);}voidadd(ll x,ll y){ll rxfind(x),ryfind(y);if(rx!ry)py[rx]ry;}intmain(){ll n;cinn;for(ll i1;in;i)py[i]i;for(ll i1;in;i)cinne[i];ll u,v;for(ll i1;in;i){cinuv;if(ne[u]ne[v])add(u,v);}for(ll i1;in;i)py[i]find(i);for(ll i1;in;i){cnt[py[i]];mxmax(mx,cnt[py[i]]);}for(ll i1;in;i){if(cnt[py[i]]mx)ans[num]i;}coutnumendl;for(ll i1;inum;i)coutans[i] ;coutans[num]endl;return0;}