Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- // Macros:
- #define f first
- #define s second
- typedef long long ll;
- typedef long double ld;
- // debugging macros
- #define db(x) cerr << #x << ": " << (x) << '\n';
- #define db_v(x) cerr << #x << ": ["; for( auto i : (x) ) cerr << i << ", "; cerr << "]\n";
- #define db_p(x) cerr << #x << ": " << (x).first << " " << (x).second << '\n';
- // random
- mt19937_64 rnd(time(0));
- unsigned long long rng (unsigned long long a, unsigned long long b){
- return uniform_int_distribution<unsigned long long>(a,b)(rnd);
- }
- unsigned long long allK;
- vector<unsigned long long> rand_val;
- vector<int> color;
- typedef vector<vector<int>> graph;
- struct centroid{
- graph G;
- vector<int> subt, boss;
- vector<unsigned long long> hash_;
- vector<bool> mk;
- int size_subt, n, root;
- set<unsigned long long> S;
- vector<int> good_path, answer;
- centroid(graph _G) {
- G = _G; n = G.size();
- subt.resize(n); mk.resize(n); boss.resize(n), hash_.resize(n);
- good_path.resize(n), answer.resize(n);
- for(int i=1; i<n; i++)
- if( !mk[i] ){
- build_centroid(i,0);
- }
- }
- void dfs_prec(int u,int p){
- subt[u] = 1;
- for( auto v : G[u] )
- if( !mk[v] && v != p ){
- dfs_prec(v,u);
- subt[u] += subt[v];
- }
- }
- /// specific code begins
- void dfs_compute(int u,int p)
- {
- if (u != p)
- {
- /// compute the hash of the path from each centroid to each node
- hash_[u] = hash_[p] + rand_val[color[u]];
- }
- /// insert the hashes in a set
- S.insert(hash_[u]);
- for( auto v : G[u] )
- if (!mk[v] && v != p)
- {
- dfs_compute(v, u);
- }
- }
- void dfs_solve(int u,int p,int centroid)
- {
- /// compute the hash needed to complement the path from the centroid to
- /// the current node u, subtracting this path and the centroid from 1 2 3 ... k
- unsigned long long hash_needed = allK - hash_[u] - rand_val[color[centroid]];
- /// check if the hash_needed is in the set, to mark all the nodes from u to centroid as solved
- /// for each path (u, v) in subt(centroid) that is a permutation, all its nodes will be marked
- /// since this part of the code will be true for (u, centroid) and for (v, centroid)
- auto it = S.lower_bound(hash_needed);
- if( it != S.end() && (*it) == hash_needed )
- {
- good_path[u] ++;
- }
- for( auto v : G[u] )
- if (!mk[v] && v != p)
- {
- dfs_solve(v, u, centroid);
- }
- }
- void dfs_accumulate(int u,int p)
- {
- for (auto v : G[u])
- {
- if (!mk[v] && v != p)
- {
- dfs_accumulate(v, u);
- /// make a bottom up accumulation to mark all the nodes from u to centroid as solved
- good_path[u] += good_path[v];
- good_path[v] = 0;
- }
- }
- /// if a node is in any good path, then its answer is YES
- if (good_path[u] > 0)
- answer[u] = 1;
- if (u == p)
- good_path[u] = 0;
- }
- /// specific code ends
- int find_centroid(int u,int p){
- for( auto v : G[u] )
- if( !mk[v] && subt[v] > size_subt / 2 && v != p )
- return find_centroid(v,u);
- return u;
- }
- void build_centroid(int nod,int p){
- dfs_prec(nod,nod);
- size_subt = subt[nod];
- int centroid = find_centroid(nod,nod);
- /// specific code
- S.clear();
- hash_[centroid] = boss[centroid] = 0;
- dfs_compute(centroid, centroid);
- dfs_solve(centroid, centroid, centroid);
- dfs_accumulate(centroid, centroid);
- /// /specific code
- mk[centroid] = 1;
- for( auto u : G[centroid] ){
- if( !mk[u] ){
- build_centroid(u,centroid);
- }
- }
- }
- };
- int main(){
- ios_base::sync_with_stdio(0); cin.tie(0);
- ///cout.setf(ios::fixed); cout.precision(10);
- //freopen("a.in","r",stdin);
- //freopen("a.in","w",stdout);
- int n, k, q;
- cin >> n >> k >> q;
- rand_val.resize(k+1);
- allK = 0;
- for(int i=1; i<=k; i++)
- {
- rand_val[i] = rng(0,1ll<<62);
- allK += rand_val[i];
- }
- color.resize(n+1);
- for(int i=1; i<=n; i++)
- {
- cin >> color[i];
- }
- graph G(n+1);
- for(int i=1; i<n; i++)
- {
- int u, v;
- cin >> u >> v;
- G[u].push_back(v);
- G[v].push_back(u);
- }
- centroid cTree = centroid(G);
- for(int i=1; i<=q; i++)
- {
- int u;
- cin >> u;
- if( cTree.answer[u] )
- cout << "YES\n";
- else
- cout << "NO\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement