killer_ash

Untitled

Apr 10th, 2020
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  1. /*                        _
  2.                        _oo0oo_
  3.                       o8888888o
  4.                       88" . "88
  5.                       (| -_- |)
  6.                       0\  =  /0
  7.                    ____/`---'\____
  8.                   /  \\|     |//  \
  9.                  / \\||| /:\ |||// \
  10.                 / _||||| -:- |||||- \
  11.                |   | \\\ \-/ /// |   |
  12.                | \_|  ''\---/''  |_/ |
  13.                \  .-\__  '-'  ___/-. /
  14.             ____'. .'  /--.--\  `. .'_____
  15.           /"" '<  `.___\_<|>_/___.' >' "" \
  16.          | | :  `- \`.;`\ _ /`;.`/ - ` : | |
  17.          \  \ `_.   \_ __\ /__ _/   .-` /  /
  18.           `-.____`.___ \_____/___.-`___.-'
  19.  
  20. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  21.     ash_1_e                     IIT Patna
  22. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
  23.  
  24. #include<bits/stdc++.h>
  25. using namespace std;
  26.  
  27. #define ll long long int
  28. #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  29. #define FRE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
  30. #define f(i,n) for(ll i=0;i<n;i++)
  31. #define fa(i,a,n) for(ll i=a;a<n?i<n:i>n;a<n?i+=1:i-=1)
  32. #define pb push_back
  33. #define F first
  34. #define S second
  35. #define all(x) x.begin(), x.end()
  36. #define clr(x) memset(x, 0, sizeof(x))
  37. #define sortall(x) sort(all(x))
  38. #define PI 3.1415926535897932384626
  39. #define MOD 1000000007
  40.  
  41. typedef pair<int, int> pii;
  42. typedef pair<ll, ll> pll;
  43. typedef vector<int> vi;
  44. typedef vector<ll> vl;
  45. typedef vector<pii> vpii;
  46. typedef vector<pll> vpll;
  47. typedef vector<vi> vvi;
  48. typedef vector<vl> vvl;
  49.  
  50. const ll mod = 1000000007;
  51. const ll N = 3e5, M = N, ninf = -2e5;
  52. vl g[N];
  53. ll a[N], dp[N], in[N], out[N];
  54. ll n;
  55.  
  56.  
  57. bool ok;
  58. ll curr_color;
  59.  
  60. bool dfs(ll u, ll par){
  61.     ok = ok && (a[u] == curr_color);
  62.     for(ll v: g[u]) {
  63.         if (v == par) continue;
  64.         dfs(v, u);
  65.     }
  66. }
  67.  
  68. bool solve(ll u){
  69.     ll ans=true;
  70.     for(ll v: g[u]){
  71.         curr_color=a[v];
  72.         ok=true;
  73.         dfs(v, u);
  74.         ans=ans && ok;
  75.     }
  76.     return ans;
  77. }
  78.  
  79. int32_t main()
  80. {
  81.     IOS
  82.     ll t,m,k,x,y,z,p,q,u,v,ct=0,flag=0,d;
  83.     cin>>n;
  84.     f(i,n-1) cin>>u>>v, g[u].pb(v), g[v].pb(u);
  85.     fa(i,1,n+1) cin>>a[i];
  86.     ll root1=-1;
  87.     ll root2=-1;
  88.     fa(i,1,n+1){
  89.         for(ll ele: g[i]){
  90.             if(a[ele]!=a[i]){
  91.                 root1=ele;
  92.                 root2=i;
  93.                 break;
  94.             }
  95.         }
  96.     }
  97.     if(root1==-1){
  98.         cout<<"YES\n1";
  99.         return 0;
  100.     }
  101.     bool res1=solve(root1);
  102.     bool res2=solve(root2);
  103.     if(res1){
  104.         cout<<"YES\n"<<root1;
  105.     }else if(res2){
  106.         cout<<"YES\n"<<root2;
  107.     }else{
  108.         cout<<"NO";
  109.     }
  110. }
Add Comment
Please, Sign In to add comment