Subtree Sizes

The subtree size of v is the number of vertices whose root path passes through v, including v itself. A leaf has size 1; the root has size N. Computing all sizes is a first example of bottom-up tree dynamic programming: solve smaller child subtrees before combining their results.

Subtree sizes appear in centroid finding, heavy-light decomposition, rerooting formulas, and counting how many pairs of vertices use an edge. This lesson focuses on the recurrence and its ordering requirement. The implementation uses a reversed parent-before-child traversal, which avoids recursion while preserving the essential dependency order.

Prerequisites: Rooted Trees and Tree Representation; DFS or BFS discovery order.

Build the idea

1. 1. Derive the recurrence from disjoint subtrees

   Fix a root and write children(v) for its children. Every vertex below v is either v itself or belongs to exactly one child subtree. Child subtrees cannot overlap: an overlapping descendant would have two different paths to v. Therefore subtree[v] = 1 + sum(subtree[child]). The initial 1 is essential because v belongs to its own subtree.

   For edges (1,2), (1,3), (3,4), (3,5), rooted at 1, leaves 2,4,5 have size 1. Vertex 3 has size 1+1+1=3. Root 1 has size 1+1+3=5. This computes every answer from smaller answers rather than traversing separately from each vertex.

2. 2. Establish a safe processing order

   During a top-down traversal, size[child] is not final when its parent is first discovered. Adding it at that moment would use incomplete information. Recursive DFS solves this by accumulating only after returning from a child. An iterative alternative first records an order in which every parent appears before its children. Either DFS discovery or BFS discovery works for that limited property.

   Reverse the order. Now every child appears before its parent, so its entire accumulated subtree size is already final. Initialize all sizes to 1, then for every nonroot v perform size[parent[v]] += size[v]. This is the same recurrence with the direction of accumulation reversed.

3. 3. Trace the iterative computation

   A BFS order for the example is 1,2,3,4,5. Reverse processing goes 5,4,3,2,1. Vertex 5 contributes 1 to 3, making size[3]=2. Vertex 4 contributes another 1, making size[3]=3. Vertex 3 contributes its complete value 3 to 1, making size[1]=4. Vertex 2 contributes 1, making size[1]=5. Root 1 has no parent and contributes nowhere.

   The BFS order itself is not a subtree interval. Its only purpose here is dependency ordering. Later Euler-tour flattening uses DFS specifically because it also needs every subtree to occupy a contiguous block.

4. 4. Interpret an edge using one subtree size

   Remove edge parent[v]–v. One component contains exactly the subtree of v and has size subtree[v]; the other contains N−subtree[v] vertices. Thus subtree[v] × (N−subtree[v]) unordered vertex pairs have their unique path crossing this edge. Store such products in long long: even when every size fits in int, a product of two sizes can overflow int.

   Subtree membership depends on the selected root. Rooting the same example at 3 makes the subtree of 1 become {1,2}, so its size changes from 5 to 2. Rebuild parents and sizes after changing roots. The two component sizes of an undirected edge remain the same pair, possibly swapped.

5. 5. Check the result with invariants

   Every size is at least 1 and at most N. A vertex with no children must have size 1. The chosen root must have size N. These conditions catch several mistakes but are not a complete proof; the disjoint-child recurrence plus child-before-parent order gives the correctness argument by induction.

   The implementation relies on a valid input tree, uses 1-based labels, and handles N=1 without special traversal code. Its root keeps parent 0 and is skipped during accumulation. The output lists values by vertex label, independently of the processing order.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,root;
    cin>>n>>root;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    // Count each vertex itself before adding child contributions.
    vector<int>parent(n+1),order,subtree(n+1,1);
    queue<int>q;
    q.push(root);
    while(!q.empty()){
        // Record a top-down order: a parent is always listed before its children.
        int v=q.front();
        q.pop();
        order.push_back(v);
        for(int next:graph[v]){
            if(next==parent[v]){
                continue;
            }
            parent[next]=v;
            q.push(next);
        }
    }
    // A reversed parent-before-child order makes all child results final.
    for(int i=n-1;i>=0;--i){
        int v=order[i];
        // The root has no parent; every other completed subtree contributes once.
        if(parent[v]!=0){
            subtree[parent[v]]+=subtree[v];
        }
    }
    for(int v=1;v<=n;++v){
        cout<<subtree[v]<<(v==n?'\n':' ');
    }
}

Complexity analysis

O(N) preprocessing time: build one traversal order and accumulate once per nonroot vertex. Each stored subtree-size query is O(1). Adjacency lists, parent/order/size arrays, and the queue use O(N) space.

Example input and output

N root, followed by N−1 undirected edges of a valid tree. Output the rooted subtree sizes of vertices 1..N.

Input

5 1
1 2
1 3
3 4
3 5

Output

5 1 3 1 1

Subtree 3 contains 3,4,5, and subtree 1 contains the whole tree. Vertices 2,4,5 each contribute only themselves.

Practical applications

Centroids use the largest component left by removing a vertex. HLD chooses a maximum-size child. Rerooting distances use N−2·subtree[child]. Edge-contribution counting uses size·(N−size).

Check your understanding

Why can a reversed BFS discovery order compute subtree sizes?

Put it into practice

For every edge parent[v]–v, print how many unordered vertex pairs have a path using that edge.