代码
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; int x[100500]; int y[100500]; int k[100500]; int t[100500]; int dfs(){ } int main(){ //freopen("in.txt","r",stdin); int i,j,l,f1,f2,t1,t2,g1,g2,n,m; cin >> n; memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); for(i=1;i<n;i++) cin >> x[i] >> y[i]; memset(k,0,sizeof(k)); memset(t,0,sizeof(t)); for(i=1;i<=n;i++) cin >> t[i]; m=0; for(i=1;i<n;i++){ if(t[x[i]]!=t[y[i]]){ //不想等表明2个点的颜色不同 m++; k[x[i]]++; k[y[i]]++; } } for(i=1;i<=n;i++){ if(m==k[i]){ cout << "YES" << endl; cout << i <<endl; return 0; } } cout << "NO" << endl; return 0; }
2个思路
#include <iostream> #include <stdio.h> #include <string.h> #include <vector> using namespace std; int x[100500]; int y[100500]; vector<int>qq[100500]; int se[100500]; int dfs(int y,int x){ //cout << " y= " << y << " x= " << x << endl; if(qq[x].size()>1||qq[x][0]!=y){ int i; int g1=0; for(i=0;i<qq[x].size();i++){ if(qq[x][i]==y)continue; g1=dfs(x,qq[x][i]); if(g1==-1){ // cout << x << "返回-1" << endl; return -1; } } }else{ // cout << y << "---" << x << endl; //cout << se[y] << " " <<se[x] <<endl; if(se[y]==se[x]){ // cout << x << "返回1" << endl; return 1; }else{ // cout << x << "返回-1" << endl; return -1; } } // cout << x << "返回???? " <<se[x] << " " <<se[y]<< endl; if(se[x]==se[y]) return 1; else return -1; } int main(){ //freopen("in.txt","r",stdin); int i,j,l,k,f1,f2,t1,t2,g1,g2,n,m; cin >> n; memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); memset(se,0,sizeof(se)); for(i=1;i<n;i++){ cin >> x[i] >> y[i]; qq[x[i]].push_back(y[i]); qq[y[i]].push_back(x[i]); } for(i=1;i<=n;i++) cin >> se[i]; for(i=1;i<n;i++){ if(se[x[i]]!=se[y[i]]){ f1=0; f2=0; for(j=0;j<qq[x[i]].size();j++){ for(k=0;k<qq[qq[x[i]][j]].size();k++){ if(qq[qq[x[i]][j]][k]==x[i])continue; f1=min(f1,dfs(qq[x[i]][j],qq[qq[x[i]][j]][k])); } } //cout << "666" << endl; for(j=0;j<qq[y[i]].size();j++){ for(k=0;k<qq[qq[y[i]][j]].size();k++){ if(qq[qq[y[i]][j]][k]==y[i])continue; f2=min(f2,dfs(qq[y[i]][j],qq[qq[y[i]][j]][k])); } } // cout << x[i] << " " << y[i] << " f1= " <<f1 << " f2= " << f2 <<endl; if(f1==0){ cout << "YES" << endl; cout << x[i] << endl; return 0; }else if(f2==0){ cout << "YES" << endl; cout << y[i] << endl; return 0; }else if(f1==-1||f2==-1){ cout << "NO" << endl; return 0; } } } cout << "YES" << endl; cout << x[1] << endl; return 0; }
