Subtree Queries C++ Solution

Formulating the approach

I’m focusing on reading the problem statement, setting the tree vertex as root, calculating subtree sizes, and ranking them. The goal is to identify the k-th smallest subtree size for each query.

Analyzing tree structure and queries

OK, let's see. With vertex 1 as the root, the subtree sizes are [1, 1, 2, 4]. For k=2, k=3, and k=4, the results are 1, 2, and 4.

Evaluating vertex roles

OK, looking at vertex 1, the subtree sizes in non-decreasing order are [1, 2, 3]. The second smallest subtree size is 2, which aligns with the query.

Mapping subtree sizes

I’m piecing together subtree sizes for each root. For vertex 2, the sorted sizes are [1, 1, 3], with the second smallest as 1. For vertex 3, the sorted sizes are [1, 2, 3], with the second smallest as 2.

Evaluating the approach

I’m analyzing the naive method's O(q * n log n) complexity. For large inputs, advanced techniques like virtual re-rooting, ETT, heavy-light decomposition, or centroid decomposition seem more efficient.

Focusing on subtree size

I’m working through calculating subtree sizes for each root with a depth-first search (DFS), optimizing with re-rooting techniques. This efficiently handles all possible roots in O(n) time.

Isolating essential data

I'm pulling together that only the k-th smallest subtree size is needed per query. This approach hones in on target data, avoiding the extra load of unnecessary size distributions.

Choosing the right fit

I'm focusing on efficiently managing subtree sizes for each root, considering sorting methods, class mappings, and using data structures like segment trees or balanced binary search trees.

Mapping efficient calculation

I’m thinking about root 1 as the base and recalculating subtree sizes for each query to ensure the k-th smallest value is achieved.

Opting for a simpler approach

Given the problem's constraints, the naive method seems to be the practical choice to identify the k-th smallest subtree size for each query.

Shifting gears

Given the lack of constraints, the naive method—rooting the tree, running DFS, sorting sizes, and picking the k-th smallest size—seems feasible for each query.

Piecing together the steps

I’m outlining plans to parse inputs, construct adjacencies, perform DFS for subtree sizes, sort them, and pinpoint the k-th smallest size for each query.

Pulling it together

Mapping out the naive approach: parsing inputs, forming adjacencies, calculating subtree sizes using DFS, sorting them, and identifying the k-th smallest size for each query.

Thought about subtree queries in trees for 32 seconds

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++:

#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.