fork(4) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 1e5;
  4. vector<int> graph[maxn + 5];
  5. bool special[maxn + 5];
  6. int A[maxn + 5];
  7. int res;
  8. int parent[maxn + 5];
  9. unordered_set<int> chalo;
  10.  
  11. void dfs(int u, int p, int col){
  12.     if(col == A[u])
  13.         special[u] = true;
  14.     if(special[u])
  15.          chalo.insert(u);
  16.     for (int i: graph[u]){
  17.         if(i == p) continue;
  18.         dfs(i, u, col);
  19.     }
  20. }
  21.  
  22. void dfs1(int u, int p){
  23.     for (int i: graph[u]){
  24.         if(i == p) continue;
  25.         parent[i] = u;
  26.         dfs1(i, u);
  27.  
  28.     }
  29. }
  30.  
  31. int main(){
  32.     int n; cin >> n; 
  33.     for (int i = 0, x,y; i < n-1; ++i){
  34.         cin >> x >> y;
  35.         graph[x].push_back(y);
  36.         graph[y].push_back(x);
  37.     }
  38.  
  39.     for (int i = 1; i <= n; ++i)
  40.         cin >> A[i];
  41.  
  42.     int q; cin >> q;
  43.     dfs1(1, -1);
  44.  
  45.     while(q--){
  46.         int x; cin >> x;
  47.         int p = parent[x];
  48.         dfs(x, parent[x], A[x]);
  49.         cout << chalo.size() << endl;
  50.  
  51.     }
  52.  
  53.  
  54. }
Success #stdin #stdout 0s 5968KB
comments (?)
stdin 
5
3 1
3 2
2 4
2 5
1 1 2 2 1
4
2
4
5
1
stdout 
2
3
3
4
https://ideone.com/whqXRa
language:
C++14 (gcc 8.3)
created:
4 years 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!