oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

stones Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

stones.html

Looking for stones to collect and deliver to the guru in exchange for a chance to ask a question, Mumble stumbles upon a tree. (Don't ask why there is a tree in 80-below-zero Antarctica. There just is.) The tree happens to have stones on it. (Again, don't ask.) But some stones are hanging on the leaves, and other hanging on the tree branch junctions. In fact, some of these junctions or leaves have more than one stone hanging on them. (Stop asking!)

Intrigued, Mumble starts to count the stones. The number of stones inexplicably happens to be the same as the number of junctions and leaves! Oh my. What a discovery. (What did I say?)

By now, Mumble has totally forgotten about his all-important task of finding stones. Having such a beautiful correspondence between the number of stones and the number of junctions and leaves feels like such a waste when the stones are all over the place. (Umm...) Determined to right this wrong, Mumble sets himself on the task of rearranging the stones such that each junction and each leaf has exactly one stone stuck to it.

Mumble can move a stone by sliding it across a tree branch. (By, uh, sliding the string?) What is the minimum number of such moves Mumble must make before each junction has exactly one stone stuck on it?

Input

The first line contains n, the number of junctions and leaves.

The following n lines contain two integers each, pi and si, representing the parent of the ith junction and the number of stones hanging on that junction.

If the junction has no parent, pi will be -1.

Output

Output a single integer indicating the minimum number of such moves Mumble must make before the tree has one stone per junction or leaf.

Limits

For 60% of test cases, 1 ≤ n ≤ 2,000.

For 100% of test cases, 1 ≤ n ≤ 1,000,000.

Sample Input 1

5
-1 0
0 0
0 2
1 0
1 3

Sample Output 1

4

Sample Input 2

7
1 3
2 0
3 0
-1 1
3 0
4 0
5 3

Sample Output 2

6

stones.jpg

stones 2.png

stones 1.png

Tags

Graph Theory, Depth First Search, RI NOI Sel Test 2012

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100102s128MBAverage
2022s128MBAverage

Judge Compile Command

g++-8 ans.cpp -o stones -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.