Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ArrayList<Integer> graph[];
- int[] c;
- int[] parentColor;
- void solve() throws IOException {
- int n = rI();
- this.graph = new ArrayList[n];
- for (int i = 0; i < n; i++) {
- graph[i] = new ArrayList<Integer>();
- }
- for (int i = 0; i < n - 1; i++) {
- int a = rI() - 1;
- int b = rI() - 1;
- graph[a].add(b);
- graph[b].add(a);
- }
- this.parentColor = new int[n];
- this.c = rA(n);
- this.used = new boolean[n];
- this.listForCheckSecond = new ArrayList<Integer>();
- this.listForCheckFirst = new ArrayList<Integer>();
- this.edge = 0;
- this.firstColor = c[0];
- this.secondColor = -2;
- this.f = false;
- dfs(0);
- Arrays.fill(used, false);
- dfs2(edge);
- if (f) {
- Arrays.fill(used, false);
- edge = 0;
- f = false;
- dfs2(0);
- if (f) {
- out.print("NO");
- } else {
- out.println("YES");
- out.println("1");
- }
- } else {
- out.println("YES");
- out.println(edge + 1);
- }
- }
- int edge;
- boolean[] used;
- ArrayList<Integer> listForCheckSecond;
- ArrayList<Integer> listForCheckFirst;
- int firstColor;
- int secondColor;
- boolean f;
- // =======================================================
- void dfs(int from) {
- used[from] = true;
- for (int i : graph[from]) {
- if (!used[i]) {
- if (c[i] != firstColor) {
- if (edge == 0) {
- edge = i;
- continue;
- } else {
- f = true;
- return;
- }
- } else {
- dfs(i);
- }
- }
- }
- }
- void dfs2(int from) {
- used[from] = true;
- for (int i : graph[from]) {
- if (!used[i]) {
- if (from == edge || c[from] == c[i]) {
- dfs2(i);
- } else {
- f = true;
- return;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment