fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>	
  3. using namespace std;
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vl;
  8. typedef pair<int, int>pi;
  9. typedef pair<ll, ll>pl;
  10. typedef vector<pi>vpi;
  11. typedef vector<pl>vpl;
  12. typedef vector<vi> vvi;
  13. typedef vector<vl> vvl;
  14. typedef vector<string> vs;
  15. typedef vector<bool> vb;
  16. const long double PI = acos(-1);
  17. const ll oo = LLONG_MAX;
  18. const int MOD = 1e9 + 7;
  19. const int N = 1e5 + 7;
  20. #define all(v) (v).begin(),(v).end()
  21. #define rall(v) (v).rbegin(),(v).rend()
  22. #define read(v) for (auto& it : v) scanf("%d", &it);
  23. #define readl(v) for (auto& it : v) scanf("%lld", &it);
  24. #define print(v) for (auto it : v) printf("%d ", it); puts("");
  25. #define printl(v) for (auto it : v) printf("%lld ", it); puts("");
  26. int n;
  27. vector<vector<int>>g(N);
  28. vector<int>c(N);
  29. bool oki = false;
  30. void DFS(int u, int p, int root) {
  31. 	for (auto& v : g[u]) {
  32. 		if (v == p)
  33. 			continue;
  34. 		if (u != root && c[v] != c[u]) {
  35. 			oki = true;
  36. 			return;
  37. 		}
  38. 		DFS(v, u, root);
  39. 	}
  40. }
  41. void init() {
  42. 	oki = false;
  43. 	for (int i = 0; i <= n; i++)
  44. 		g[i].clear(), c[i] = 0;
  45. }
  46. void solve() {
  47. 	scanf("%d", &n);
  48. 	init();
  49. 	for (int i = 0; i < n - 1; i++) {
  50. 		int u, v;
  51. 		scanf("%d %d", &u, &v);
  52. 		u--, v--;
  53. 		g[u].push_back(v);
  54. 		g[v].push_back(u);
  55. 	}
  56. 	for (int i = 0; i < n; i++)
  57. 		scanf("%d", &c[i]);
  58. 	vector<int>roots;
  59. 	for (int u = 0; u < n; u++) {
  60. 		for (auto& v : g[u]) {
  61. 			if (c[u] != c[v]) {
  62. 				roots.push_back(u);
  63. 				roots.push_back(v);
  64. 				break;
  65. 			}
  66. 		}
  67. 		if (!roots.empty())
  68. 			break;
  69. 	}
  70. 	if (roots.empty()) {
  71. 		printf("YES\n1\n");
  72. 		return;
  73. 	}
  74. 	for (auto& it : roots) {
  75. 		oki = false;
  76. 		DFS(it, -1, it);
  77. 		if (!oki) {
  78. 			printf("YES\n%d\n", it + 1);
  79. 			return;
  80. 		}
  81. 	}
  82. 	puts("NO");
  83. }
  84. int t = 1;
  85. int main() {
  86. #ifndef ONLINE_JUDGE
  87. 	freopen("input.txt", "r", stdin);
  88. #endif
  89. 	//scanf("%d", &t);
  90. 	while (t--) solve();
  91. }
Success #stdin #stdout 0.01s 6088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
1
https://ideone.com/RyZpKQ
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!