Subtree Queries C++ Solution

Below is a straightforward ("naive") C++ implementation that should work correctly for smaller constraints.

Important note on complexity:

• For each query, we do a DFS to compute subtree sizes (O(n)), then sort them (O(n log n)).
• If $q$ is the number of queries and $n$ is the number of vertices, this naive approach can take $O(q \times (n + n\log n)) = O(q \times n \log n)$.

This will be too slow for very large $n$ and $q$ (e.g., $10^5$). However, if your input constraints are moderate (e.g., $n \le 10^4$ or the total queries are not too large), this approach can pass.

For larger constraints, an advanced “re-rooting” technique or offline data-structure approach would be required. Since the problem statement doesn’t specify maximum limits, here is the clear and direct solution in C++:

cpp
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200000; // Adjust if needed, or remove if constraints are small.

vector<int> adj[MAXN + 1];
vector<int> subtreeSize;
int n, q;

// A simple DFS to compute the size of the subtree rooted at `u` (with parent `p`).
int dfs_subtree(int u, int p)
{
    int sz = 1;  // count current node
    for(int v : adj[u])
    {
        if(v == p) continue;  // don't go back to parent
        sz += dfs_subtree(v, u);
    }
    subtreeSize[u] = sz;
    return sz;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    
    // Read edges
    // We have n - 1 edges for an n-vertex tree (the statement "0 <= i < n" is a bit confusing,
    // typically a tree has n-1 edges. Adjust if needed.)
    for(int i = 0; i < n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        // Build undirected adjacency
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    cin >> q;
    
    // We'll answer each query
    // For each query x, k:
    //  1) Root the tree at x
    //  2) DFS to compute subtree sizes for all nodes
    //  3) Sort the subtree sizes
    //  4) Output the k-th smallest
    while(q--)
    {
        int x, k;
        cin >> x >> k;
        
        // Prepare subtreeSize array (index from 1..n)
        subtreeSize.assign(n+1, 0);
        
        // Compute subtree sizes with root = x
        dfs_subtree(x, -1);
        
        // Now collect all subtree sizes
        // (note that subtreeSize[u] is only valid for visited nodes,
        //  but in a tree DFS from root x visits all of them anyway)
        vector<int> sizes;
        sizes.reserve(n);
        for(int i = 1; i <= n; i++)
            sizes.push_back(subtreeSize[i]);
        
        // Sort
        sort(sizes.begin(), sizes.end());
        
        // k-th smallest is sizes[k-1] in 0-based indexing
        cout << sizes[k-1] << "\n";
    }
    
    return 0;
}

Explanation of the Key Steps

1. Reading Input / Building Adjacency
   We read $n$ (the number of vertices) and then read each of the $n-1$ edges (assuming a proper tree). For each edge $(a, b)$, we record the undirected relationship:

   $$\text{adj}[a].push\_back(b),\quad \text{adj}[b].push\_back(a).$$

2. Handling Each Query
   Each query gives us a root $x$ and an integer $k$.

   • We call dfs_subtree(x, -1) to do a depth-first search from $x$, ignoring the parent edge, and accumulate subtree sizes in a global or external array subtreeSize[u].
   • After the DFS completes, subtreeSize[u] is the size of the subtree rooted at $u$ when $x$ is considered the overall root.
   • We then collect all subtreeSize[u] values for $u = 1..n$ into a vector<int> sizes and sort them in non-decreasing order.
   • The $k$-th smallest subtree size (1-based) is sizes[k-1] in 0-based indexing.

3. Output
   We simply print the answer for each query immediately (or store it to print later).

If you need to handle very large $n$ and $q$
You would need an approach more advanced than the naive “DFS + sort” per query. Common strategies might include:

• Heavy-Light Decomposition or a centroid decomposition based approach.
• A single DFS + dynamic programming re-root technique (sometimes called “all-roots DP” or “tree DP for re-rooting”) can compute certain aggregates in $O(n)$. However, retrieving the entire sorted list of subtree sizes per re-root still poses a challenge.
• Some forms of offline queries with an Euler Tour + Fenwick Tree/Segment Tree structure might help if the queries can be cleverly transformed (though non-trivial for subtree-size distributions).

But unless you have tight time constraints and large inputs, the above naive solution is the simplest way to code the logic.