Proficient.
Put your skills to the test.

Problem summary

A company is a rooted tree with CEO1. A query chooses an ancestor p of employee c and makes every vertex on the current c-to-p path except p a direct child of p. After each query, output the sum of employee depths.

Source clarification. The explicit path method is the official full-solution approach. Its aggregate bound follows from the quadratic decrease per long path; no dynamic-tree or inverse-Ackermann bound is assumed. Editorial: https://infos.infosbg.com/files/Contests/ETI/2025/C/analyses/managers_analysis.pdf

Constraints

1 ≤ N,Q ≤100000; root1; every query’s p is a proper current ancestor of c.

Worked example

Original statement sample.

9 4
1 2
1 3
3 4
3 5
4 6
4 7
5 8
8 9
1 3
1 4
1 8
1 7

19
16
11
10

Solution analysis

1. The sum of depths equals the sum of subtree sizes over nonroot vertices: every vertex contributes once for each ancestor edge. Initialize current parent pointers and subtree sizes using an iterative traversal to avoid recursion on a100000-vertex chain.
2. For a query, collect its current path bottom-up as v0=c,v1,...,v(h−1), where the last vertex is already a child of p. Before changing sizes, subtract size[v0]+...+size[v(h−2)] from the total. Then replace each path vertex’s subtree size by its old size minus the old size of the previous, lower path vertex (with zero below c), and set its parent to p. Branches outside the path stay attached to their own vertex.
3. Why does that subtraction work? The disjoint part belonging to vj has size oldSize[vj]−oldSize[v(j−1)] and moves upward by h−1−j levels. Summing these products telescopes to the stated sum of old subtree sizes. In the source example, the first query promotes an existing child and keeps the initial total19; later promotions yield16,11,10.

Why it works

The disjoint path-part argument accounts for every moved vertex exactly once and leaves all other depths unchanged. The updated subtree sizes remove exactly the lower path component from each ancestor; p retains its whole subtree. Current parent pointers therefore represent the new tree, and the maintained sum stays correct by induction.

Watch out. Follow current parent pointers, not the original tree. Read old sizes before replacing them. A direct-child promotion changes nothing. Use long long for the depth sum; it can approach N(N−1)/2.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<vector<int>>children(n+1);
    vector<int>parent(n+1,0),size(n+1,1);
    for(int i=1;i<n;i++){
        int manager,employee;
        cin>>manager>>employee;
        parent[employee]=manager;
        children[manager].push_back(employee);
    }
    vector<int>order(1,1);
    for(int index=0;index<static_cast<int>(order.size());index++){
        for(int child:children[order[index]]){
            order.push_back(child);
        }
    }
    long long total=0;
    for(int index=n-1;index>0;index--){
        int vertex=order[index];
        total+=size[vertex];
        size[parent[vertex]]+=size[vertex];
    }
    vector<int>path;
    while(q--){
        int manager,employee;
        cin>>manager>>employee;
        path.clear();
        for(int vertex=employee;vertex!=manager;vertex=parent[vertex]){
            path.push_back(vertex);
        }
        for(int i=0;i+1<static_cast<int>(path.size());i++){
            total-=size[path[i]];
        }
        int previousOldSize=0;
        for(int vertex:path){
            int oldSize=size[vertex];
            // Remove the lower path's old subtree, but keep side branches.
            size[vertex]=oldSize-previousOldSize;
            previousOldSize=oldSize;
            parent[vertex]=manager;
        }
        cout<<total<<'\n';
    }
}