party-invites.cpp

vector < vector <int> > adj;
int attending[N];

void dfs(int i, int par){
  int sm = 0;
  for(auto j: adj[i]){
    if(j == par)
      continue;
    dfs(j, i); // call dfs on child node to compute its answer
    sm += attending[j]; // add to the sum
  }
  attending[i] = sm + 1;
}

int main(){
  int n; // # nodes, hopefully n <= N 
  cin >> n;
  // get the tree input and build the adj list representation
  for(int i = 0, x, y; i < n; ++i){
    cin >> x >> y;
    adj[x].pb(y);
    adj[y].pb(x);
  }
  // run DFS once to compute all answers O(n)
  dfs(1, -1);
  int q;  // # queries
  cin >> q;
  while(q--){
    cin >> m; // member node id
    cout << attending[m] << endl; // O(1)
  }
}