Submission #73908776

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
#define INF 1e18
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl "\n"
#define vi vector<int>
#define vs vector<string>
#define pii pair<int, int>
#define mii map<int, int>
#define seti set<int>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define pr(a) cout<<a<<endl;
#define printList(a) for (auto &x : a) cout << x << " ";cout<<endl;
#define printMap(a) for (auto &x : a) cout << x.ff << " " << x.ss << endl;
#define PI 3.1415926535897932384626
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x
#define w(x) int x; cin>>x; while(x--)
#define sortall(x) sort(all(x))
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vpii vector<pii>
#define matrix(N,M) vvi matrix(N, vi(M, 0));
#define printMatrix(matrix) for(auto &x:matrix){for(auto &y:x)cout<<y<<" ";cout<<endl;}
#define inputMatrix(matrix) for(auto &x:matrix)for(auto &y:x)cin>>y;
#define sortMatrix(matrix) for(auto &x:matrix)sortall(x);
#define rotateMatrix(matrix) reverse(all(matrix));for(int i=0;i<matrix.size();i++)for(int j=0;j<i;j++)swap(matrix[i][j],matrix[j][i]);
#define matrixSum(matrix) int sum=0;for(auto &x:matrix)for(auto &y:x)sum+=y;cout<<sum<<endl;
#define matrixProduct(matrix) int product=1;for(auto &x:matrix)for(auto &y:x)product*=y;cout<<product<<endl;
#define matrixMax(matrix) int mx=INT_MIN;for(auto &x:matrix)for(auto &y:x)mx=max(mx,y);cout<<mx<<endl;
#define matrixMin(matrix) int mn=INT_MAX;for(auto &x:matrix)for(auto &y:x)mn=min(mn,y);cout<<mn<<endl;
#define matrixTranspose(matrix) for(int i=0;i<matrix.size();i++)for(int j=0;j<i;j++)swap(matrix[i][j],matrix[j][i]);
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define maxEle(a) *max_element(all(a))
#define minEle(a) *min_element(all(a))
#define sumEle(a) accumulate(all(a),0)
#define productEle(a) accumulate(all(a),1,multiplies<int>())
#define maxIndex(a) max_element(all(a))-a.begin()
#define minIndex(a) min_element(all(a))-a.begin()
#define findIndex(a,x) find(all(a),x)-a.begin()
#define findEle(a,x) find(all(a),x)!=a.end()
#define countEle(a,x) count(all(a),x)
#define lowerEle(a,x) lower_bound(all(a),x)-a.begin()
#define upperEle(a,x) upper_bound(all(a),x)-a.begin()
#define gcd(a,b) __gcd(a,b)
#define hi cout<<"Hello\n";
#define yes cout<<"Yes\n";
#define no cout<<"No\n";

int Binary_exp(int a, int b, int c ){
    int ans = 1;
    while(b){
        if(b&1){
            ans =(ans*1LL*a) % c;
        }
        a = (a*1LL*a) % c;
        b/=2;
    }
    return ans;
}

int C(int n, int r) { if (r > n - r) r = n - r; int ans = 1; for (int i = 1; i <= r; i++) { ans *= n - r + i; ans /= i; } return ans; }
int modInv(int a) { return Binary_exp(a, MOD - 2, MOD); }
bool isPrime(int n){ if(n<=1)return false; for(int i=2;i*i<=n;i++)if(n%i==0)return false; return true; }

template<class T>ostream &operator<<(ostream &os,const vector<T> &p){for(auto &it:p)os<<it<<' ';return os;}
template<class T>void dbs(string str,T t){cerr<<str<<":"<<t<<endl;}
template<class T,class...S>void dbs(string str,T t,S... s){int idx=str.find(',');cerr<<str.substr(0,idx)<<":"<<t<<",";dbs(str.substr(idx+1),s...);}

const int max_n = 200005;
vector<int> adj[max_n];
int a[max_n];
string ans[max_n];
map<int, int> cnt;

void dfs(int u, int p, bool flag) {
    cnt[a[u]]++;
    
    bool flag1 = flag || (cnt[a[u]] > 1);
    
    if (flag1) {
        ans[u] = "Yes";
    } else {
        ans[u] = "No";
    }
    
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u, flag1);
        }
    }
    
    // backtrack
    cnt[a[u]]--;
}

void solved(){
    int n;
    cin>>n;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    dfs(1, 0, false);
    
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solved();
    }
    return 0;
}

Submission Info

Judge Result