1872. Snowmen

Winter. The 2012 year. Against the backdrop of coming apocalypse and the end of the world, the news passed unnoticed about the latest breakthroughs in the areas of cloning and snowmen: the snowmen cloning. You certainly know, but we remind you, that the snowman consists of zero or more balls, vertically stacked on each other, and cloning is the process of creating an identical copy (clone).

In the place Mestyachkovo the teacher Andrey Sergeevich Uchitel purchased through the online store "Shop apparatus cloning" the device for snowmen cloning. Now even kids can play and they do play in the yard the next game. From time to time one of the kids chooses the snowman he likes, clones it and:

· either adds the ball to the top;

· or removes the top ball (if the snowman is not empty).

The teacher Andrey Sergeevich Uchitel wrote the sequence of actions and now wants to know the total mass of all built snowmen.

Input. The first line contains the number of actions n (1 ≤ n ≤ 200000). The line i + 1 describes the action:

t m – clone the snowman number t (0 ≤ t < i) and add the ball to the top of weight m (0 < m ≤ 1000);

t 0 – clone the snowman number t (0 ≤ t < i) and remove the top ball. It is guaranteed that the snowman is not empty.

The result of action i, which is described in line i + 1 is a new snowman number i. Initially there is an empty snowman with number zero.

All input numbers are integer.

Output. Print the total mass of all built snowmen.

Sample Input

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

Sample Output

74

SOLUTION

data structures – persistent stack

Algorithm analysis

Information about the snowmen will be stored in the vector of structures Man. The structure Man contains the weight of snowman, and the number of its parent – the number of snowman that was cloned to obtain the current one.

· If we get i-th snowman from the t-th (t < i) by adding a ball of snow with weight m, then asssign to v[i] the snowman with parameters Man(v[t].Weight + m, t).

· If we get i-th snowman from the t-th (t < i) by removing the top ball, then we get the snowman from which the t-th one was cloned (the number of snowman from which the t-th was cloned, is located at v[t].Parent). So we must assign v[v[t].Parent] to v[i].

Let the first snowman is get from itself and has weight 0. Assign to v[0] the snowman Man(0, 0).

Sample

Consider the example of snowmen cloning process. In the picture below at the top of each snowman we put its mass.

The sixth snowman is obtained from the fifth by removing the top ball. Therefore it should coincide with the fourth snowman (from which we get the fifth). However, since the fourth snowman is obtained from the third one by adding a ball, we can regard that the sixth snowman is cloned from the third one by adding a ball of mass 2.

The eighth snowman is obtained from the first one by removing the upper ball. So it will be equal to zero snowman. But as the zero’s snowman is obtained from the zero’s, then the eighth snowman is cloned from zero’s one.

Algorithm realization

Declare the vector of pairs (or vector of structures Man) v where we store the information about snowmen.

struct Man

{

int Weight;

int Parent;

Man(int Weight, int Parent) : Weight(Weight), Parent(Parent) {};

};

vector<Man> v;

Моделируем процесс создания снеговиков как описано в анализе задачи.

scanf("%d",&n); sum = 0;

v.push_back(Man(0,0));

for(i = 1; i <= n; i++)

{

scanf("%d %d",&t,&m);

if (m > 0) v.push_back(Man(v[t].Weight + m, t));

else v.push_back(v[v[t].Parent]);

sum += v[i].Weight;

}

Выводим искомую суммарную массу снеговиков.

printf("%lld\n",sum);

Реализация при помощи статического массива

#include <stdio.h>

struct Pair

{

int Number;

int Weight;

} Sman[200001];

int i, n, t, m;

long long sum;

int main(void)

{

scanf("%d",&n); sum = 0;

for(i = 1; i <= n; i++)

{

scanf("%d %d",&t,&m);

if (m > 0)

{

Sman[i].Number = t;

Sman[i].Weight = Sman[t].Weight + m;

}

else Sman[i] = Sman[Sman[t].Number];

sum += Sman[i].Weight;

}

printf("%lld\n",sum);

return 0;

}

Java реализация

Реализуем класс Pair.

import java.util.*;

public class Main

{

public static class Pair

{

int First, Second;

public Pair(int First, int Second)

{

this.First = First;

this.Second = Second;

}

}

public static void main(String[] args)

{

Pair v[] = new Pair[200010];

v[0] = new Pair(0,0);

Scanner con = new Scanner(System.in);

int n = con.nextInt();

long sum = 0;

for(int i = 1; i <= n; i++)

{

int t = con.nextInt(), m = con.nextInt();

if (m > 0)

v[i] = new Pair(t,v[t].Second + m);

else v[i] = v[v[t].First];

sum += v[i].Second;

}

System.out.println(sum);

}

}