Biết rằng đồ thị đã cho là một cây. Vì thế, ta nhận thấy điều kiện với đỉnh ~i~ bị chiếm đóng, trong ~n-1~ đỉnh còn lại, những đỉnh có thể đến được với nhau phải có cùng chỉ số chiến thuật, đồng nghĩa với việc khi bỏ đi đỉnh ~i~, những đỉnh thuộc cùng một thành phần liên thông (đến được nhau) phải có cùng chỉ số chiến thuật.

Điều trên đồng nghĩa với việc nếu ~i~ là một đỉnh thỏa mãn, thì sau khi bỏ đỉnh ~i~ (cùng các cạnh nối với ~i~), tất cả các cạnh còn lại đều là cạnh nối ~2~ đỉnh có cùng chỉ số chiến thuật.

Gọi ~tot~ là tổng số lượng cạnh ~i-j~ mà ~c_i \neq c_j~ trong ~n-1~ cạnh đã cho.

Gọi ~cnt_u~ là số lượng cạnh ~u-v~ mà ~c_u \neq c_v~.

Khi đó nếu ~tot - cnt_u = 0~ thì đỉnh ~u~ sẽ là đỉnh thỏa mãn.

~tot~ và mảng ~cnt~ có thể được tính dễ dàng trong ~O(N)~.

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 2E6;

int f[N+9];
vector<int> adj[N+9];
int n;
int c[N+9];
vector<int> res;

void dfsDown(int u,int p)
{
    f[u] = c[u];

    for (int i = 0;i < (int)adj[u].size(); ++i)
    {
        int v = adj[u][i];
        if (v == p) continue;

        dfsDown(v, u);
        if (f[v] != c[u]) f[u] = -1;
    }
}

void ck(int u,int p)
{
    bool flag = false;

    for (int i = 0;i < (int)adj[u].size(); ++i)
    {
        int v = adj[u][i];
        if(v == p) continue;

        if (f[v] < 0) flag = true;
    }

    if (flag == false) res.push_back(u);

    if (u != p && c[p] != c[u]) return;

    int chosenNode = -1;
    for (int i = 0;i < (int)adj[u].size(); ++i)
    {
        int v = adj[u][i];
        if (v == p) continue;

        if (f[v] != c[u])
        {
            if (chosenNode < 0) chosenNode = v;
            else return;
        }
    }

    if (chosenNode > 0) ck(chosenNode, u);
}

int main()
{
    fastIO

    cin>>n;

    for (int i = 1;i < n; ++i)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1;i <= n; ++i) cin>>c[i];

    try
    {
        bool flag = false;

        for (int i = 1;i+1 <= n; ++i)
            if (c[i] != c[i+1])
            {
                flag = true;
                break;
            }

        if (flag == false) throw 2;

        dfsDown(1, 1);
        ck(1, 1);
    }
    catch (int x)
    {
        if (x == 2)
        {
            cout<<"YES\n";

            for (int i = 1;i <= n; ++i) cout<<i<<" ";

            return 0;
        }
    }

    if ((int)res.size() == 0) return cout<<"NO", 0;

    cout<<"YES\n";

    sort(res.begin(),res.end());

    for (int i = 0;i < (int)res.size(); ++i) cout<<res[i]<<" ";
}