题意 ： 给出一颗树 每个点都有一个颜色 选一个点作为根节点 使它的子树各自纯色
我想到了缩点后check直径 当<=3的时候可能有解 12必定有解 3的时候需要check直径中点的组成点里是否有一个点连接了另外所有的点 如果有就是ans 没有就是no
这个方法是对了 不过比较麻烦..需要很多check
但是看div1的做法 有很棒的姿势用来解这个题
扫一下所有的边 如果两边的点颜色不一样 就增加一个连通分量数 这样可以很方便的算出有多少连通分量 同时记录这个点连着多少个其余的颜色(连通分量)
然后扫一下所有的点 看哪个点连着其余的连通分量 如果存在就是ans 没有就是no
果然还是应当多看一下别人的解法来学习 大写的服字 QAQ
我的迷茫解法 ：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define L long long
int n ;
vector<int >q[100050] ;
int c[100050] ;
int id[100050] ;
int gm[100050];
int cnt ;
void bfs(int s) {
queue<int >que ;
que.push(s) ;
while(!que.empty()) {
int u = que.front();
que.pop();
for(int i = 0; i <q[u].size(); i ++ ) {
int v = q[u][i];
if(id[v] == -1 && c[v] == c[u]) {
id[v] = cnt ;
gm[cnt] ++ ;
que.push(v) ;
}
}
}
}
vector<int >w[100050] ;
int vis[100050] ;
int res[100050];
int main(){
scanf("%d",&n) ;for(int i = 1; i <=n;i++)q[i].clear();
for(int i = 1; i < n ; i ++ ) {
int u , v;
scanf("%d%d",&u,&v);
q[u].push_back(v);
q[v].push_back(u);
}
for(int i = 1; i<=n;i++)scanf("%d",&c[i]) ;
cnt = 0;
memset(id,-1,sizeof(id)) ;
memset(gm,0,sizeof(gm));
for(int i = 1; i <= n ;i ++ ) {
if(id[i]==-1){
cnt ++ ;
id[i] = cnt ;
gm[cnt] = 1;
bfs(i) ;
res[cnt] = i ;
}
}
if(cnt == 1) {
printf("YES\n");
printf("1\n");
return 0 ;
}
if(cnt == 2) {
printf("YES\n");
for(int i = 1; i <= n ; i ++ ){
for(int j = 0 ; j < q[i].size() ; j ++) {
int v = q[i][j] ;
if(c[i]!=c[v]) {
printf("%d\n",i);
return 0;
}
}
}
}
for(int i = 1; i <= cnt ; i ++ )w[i].clear() ;
for(int i = 1 ; i <= n ; i ++ ){
for(int k = 0; k < q[i].size(); k ++ ){
int v = q[i][k] ;
if(id[v] != id[i]) {
int uu = id[i] ;
int vv = id[v] ;
w[uu].push_back(vv);
}
}
}
int d = 0;
int ans = 0;
for(int i = 1; i <= cnt ;i ++ ){
if(w[i].size() >= 2 ){
d ++ ;
if(d > 1){
ans = -1;
break ;
}
else {
ans = i ;
}
}
}
if(ans!= -1 && d == 1){
int rr = -1;
int cn = 0;
for(int i = 1 ; i <= n ; i ++ ) {
if(id [i] == ans ){
int bb = 0;
for (int j = 0 ; j < q[i].size(); j ++ ){
int v = q[i][j] ;
if(id[v] != id[i])bb ++ ;
}
if(bb == w[ans].size()) {
rr = i ;
cn ++ ;
}
}
}
if(cn == 1) {
printf("YES\n");
printf("%d\n",rr) ;
}
else printf("NO\n") ;
}
else printf("NO\n") ;
}
学习的姿势 ：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define L long long
int x[100050] ;
int y[100050] ;
int c[100050] ;
int n ;
int a[100050] ;
int main(){
scanf("%d",&n) ;
for(int i = 1; i < n ; i ++ ){
scanf("%d%d",&x[i] , &y[i]) ;
}
for(int i = 1; i <= n ; i ++ ){
scanf("%d",&c[i]) ;
}
memset(a , 0 , sizeof(a)) ;
int b = 0 ;
for(int i = 1 ; i < n ; i ++ ){
if(c[x[i]] != c[y[i]]) {
b ++ ;
a[x[i]] ++ ;
a[y[i]] ++ ;
}
}
int ans = -1 ;
for(int i = 1 ; i <= n ; i ++ ){
if(a[i] == b) {
ans = i;
break ;
}
}
if(ans == -1 )printf("NO\n") ;
else {
printf("YES\n");
printf("%d\n",ans) ;
}
}