Proficient.
Put your skills to the test.

Problem summary

Snowman 0 is empty. Operation i clones an earlier snowman p, then adds a ball of mass m if m>0, or removes its top ball if m=0. Find the sum of masses of all N newly created snowmen.

Constraints

1 ≤ N ≤ 1000000; 0 ≤ m ≤ 1000. Every removal is from a nonempty snowman.

Worked example

An independently prepared example for this explanation.

8
0 1
1 5
2 4
3 2
4 3
5 0
6 6
1 0

74

Solution analysis

1. Represent a snowman by the node for its top ball in an immutable linked stack. Each node stores the mass of its entire stack and a parent pointer to the stack below its top ball. Node 0 represents the empty stack.
2. When adding a ball, create node i whose parent is the root of snowman p and whose total mass is the parent total plus m. When removing, let the new snowman point directly to the parent of the old root. Existing nodes never change, so cloned histories safely share structure.
3. The example creates masses 1,6,10,12,15,12,18,0. Removing from snowman 5 reuses the state below its top ball, while the original snowman 5 remains mass 15. Summing the eight new masses gives 74.

Why it works

Inductively every root points to a stack with exactly that snowman’s balls and correct mass. Addition creates the specified ball above the cloned root; removal selects exactly the old root’s parent. Neither operation changes older nodes. Therefore every recorded mass is correct, and accumulating it counts all newly created snowmen.

Watch out. After removal, future clones must use the resulting root, not the operation index as a ball node. The sum can be about 5×10^14, requiring 64-bit arithmetic.

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;
    cin>>n;
    vector<int>root(n+1,0),parent(n+1,0);
    vector<long long>mass(n+1,0);
    long long answer=0;
    for(int i=1;i<=n;++i){
        int previous,ball;
        cin>>previous>>ball;
        if(ball>0){
            parent[i]=root[previous];
            mass[i]=mass[parent[i]]+ball;
            root[i]=i;
        }
        else{
            // Reuse the immutable stack below the removed top ball.
            root[i]=parent[root[previous]];
        }
        answer+=mass[root[i]];
    }
    cout<<answer<<'\n';
}