Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.48 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. if(!dfs1(to, v)){
  35. return 0;
  36. }
  37. }
  38. }
  39. return 1;
  40. }
  41. /*
  42. 4
  43. 1 2
  44. 2 3
  45. 3 4
  46. 1 2 1 1
  47. */
  48. int main(){
  49. int n;
  50. cin >> n;
  51. sp.resize(n);
  52. col.resize(n);
  53. for(int i = 0; i < n - 1; i++){
  54. int a, b;
  55. cin >> a >> b;
  56. a--, b--;
  57. sp[a].pb(b);
  58. sp[b].pb(a);
  59. }
  60. for(int i = 0; i < n; i++){
  61. cin >> col[i];
  62. }
  63. dfs(0, 0);
  64. //cout << d << endl;
  65. if(d == INF){
  66. cout << "YES" << endl;
  67. cout << 1;
  68. }
  69. else{
  70. bool ch = dfs1(d, d);
  71. if(!ch){
  72. cout << "NO";
  73. }
  74. else {
  75. cout << "YES" << endl;
  76. cout << d;
  77. }
  78. }
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement