Proficient.
Put your skills to the test.

Problem summary

Given a rooted employee hierarchy, answer how many strict descendants each queried employee has. Employee numbers need not follow the hierarchy.

Constraints

1 ≤ N ≤ 100000; 1 ≤ U,V,M ≤ N; 1 ≤ Q ≤ N; the relations form a rooted tree.

Worked example

An independently prepared example for this explanation.

4
1 3
2 1
2 4
3
1
2
4

1
3
0

Solution analysis

1. Record the parent and children of each employee. The root is the unique employee without a parent; it need not be employee 1.
2. Build an iterative traversal order with each parent before its children. Process that order backwards, adding each child’s subtree size to its parent. Initialize every subtree size to one for the employee itself.
3. In the sample, employee 2 is the root, with children 1 and 4; employee 1 has child 3. Subtree sizes are 4 for employee 2, 2 for employee 1, and 1 for leaves 3 and 4. Subtract one to get answers 3,1,0.

Why it works

In reverse traversal order all children are processed before their parent. Their disjoint subtrees, together with the parent itself, form exactly the parent’s subtree, so summing their sizes is correct by induction. Strict descendants exclude the queried employee, giving subtreeSize−1.

Watch out. Do not assume the root is 1. Exclude the employee from their own subordinate count. Iterative traversal avoids recursion depth failure on a chain.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
// Algorithm: Record the parent and children of each employee.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>children(n+1);
    vector<int>parent(n+1,0),size(n+1,1);
    for(int i=1;i<n;++i){
        int boss,employee;
        cin>>boss>>employee;
        parent[employee]=boss;
        children[boss].push_back(employee);
    }
    int root=1;
    while(parent[root]!=0){
        root=parent[root];
    }
    vector<int>order(1,root);
    for(int i=0;i<static_cast<int>(order.size());++i){
        for(int child:children[order[i]]){
            order.push_back(child);
        }
    }
    for(int i=n-1;i>0;--i){
        int employee=order[i];
        size[parent[employee]]+=size[employee];
    }
    int queries;
    cin>>queries;
    while(queries--){
        int employee;
        cin>>employee;
        cout<<size[employee]-1<<'\n';
    }
}