[Luogu]CF763ATimofeyandatree

写了我一个小时 卧槽 卡死了我了
一开始以为是 并查集缩点然后 dfs枚举
结果WA了 搞得头疼 然后看了一下题解 &＃xff1f; &＃xff1f; &＃xff1f; &＃xff1f; 直接枚举就行&＃xff1f;

• 先处理 出来 有多少个分支 (即两个结点的颜色不同)
• 然后再利用 dfs枚举每一个结点作为 根结点
• 利用分支数相同这个 特点进判断

虽然思路很简单 就一个枚举
但是总感觉卡时间复杂度了 n &＃61;1e5跑一遍全图 也就是n*(n-1)/2 (emm)

还有就是dfs 好久没写了 感觉还挺难emm

#include
using namespace std;
const int N &＃61; 4e5&＃43;10;
int cnt;
int h[N],e[N],ne[N],idx,c[N];
int n,a,b;
void add(int a,int b)
{e[idx] &＃61; b,ne[idx] &＃61; h[a],h[a]&＃61;idx&＃43;&＃43;;
}void dfs(int x,int b)
{for(int i &＃61; h[x]; i!&＃61;-1; i&＃61;ne[i]){int j &＃61; e[i];if(j &＃61;&＃61; b) continue;if(c[x]!&＃61;c[j])cnt&＃43;&＃43;;dfs(j,x);}
}void solve()
{cin>>n;memset(h,-1,sizeof h);for(int i &＃61; 1; i<&＃61;n-1; i&＃43;&＃43;){cin>>a>>b;add(a,b);add(b,a);}for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)cin>>c[i];dfs(1,0);for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){int sum &＃61; 0;for(int j &＃61; h[i]; j!&＃61;-1; j&＃61;ne[j]){// cout<<"debug"<int p &＃61; e[j];if(c[p]!&＃61;c[i])sum&＃43;&＃43;;}if(sum &＃61;&＃61; cnt){cout<<"YES"<<endl;// puts("YES");cout<<i<<endl;return;}}cout<<"NO"<<endl;//puts("NO");}
int main()
{ios::sync_with_stdio(false);solve();return 0;
}