Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.43 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. using namespace std;
  4. vector<vector<int> > sp;
  5. vector<int> col;
  6. int INF = 1e9;
  7. int d = INF;
  8.  
  9. bool dfs(int v, int p){
  10. if(p != 0){
  11. if(col[v] != col[p]){
  12. d = p;
  13. return 0;
  14. }
  15. }
  16. for(auto i : sp[v]){
  17. if(i != p) dfs(i, v);
  18. }
  19. }
  20.  
  21. int dfs1(int v, int p){
  22. cout << "vxod ";
  23. if(p != d){
  24. if(col[v] != col[p]){
  25. cout << "badaBOOM " << v + 1 << ' ' << col[v] << ' ' << p + 1 << ' ' << col[p] << ' ';
  26. return 0;
  27. }
  28. }
  29. cout << "!!!!!! ";
  30. for(int i = 0; i < sp[v].size(); i++){
  31. int to = sp[v][i];
  32. cout << v + 1 << ' ' << p + 1 << ' ' << to + 1 << '\n';
  33. if(to != p){
  34. dfs1(to, v);
  35. }
  36. }
  37.  
  38. }
  39. /*
  40. 4
  41. 1 2
  42. 2 3
  43. 3 4
  44. 1 2 1 1
  45. */
  46. int main(){
  47. int n;
  48. cin >> n;
  49. sp.resize(n);
  50. col.resize(n);
  51. for(int i = 0; i < n - 1; i++){
  52. int a, b;
  53. cin >> a >> b;
  54. a--, b--;
  55. sp[a].pb(b);
  56. sp[b].pb(a);
  57. }
  58. for(int i = 0; i < n; i++){
  59. cin >> col[i];
  60. }
  61. dfs(0, 0);
  62. //cout << d << endl;
  63. if(d == INF){
  64. cout << "YES" << endl;
  65. cout << 1;
  66. }
  67. else{
  68. bool ch = dfs1(d, d);
  69. if(!ch){
  70. cout << "NO";
  71. }
  72. else {
  73. cout << "YES" << endl;
  74. cout << d;
  75. }
  76. }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement