[Solution] Path Prefixes solution codeforces

Path Prefixes solution codeforces – You are given a rooted tree. It contains 𝑛n vertices, which are numbered from 11 to 𝑛n. The root is the vertex 11.

Table of Contents

[Solution] Path Prefixes solution codeforces

Each edge has two positive integer values. Thus, two positive integers 𝑎𝑗aj and 𝑏𝑗bj are given for each edge.

Output 𝑛1n−1 numbers 𝑟2,𝑟3,,𝑟𝑛r2,r3,…,rn, where 𝑟𝑖ri is defined as follows.

Consider the path from the root (vertex 11) to 𝑖i (2𝑖𝑛2≤i≤n). Let the sum of the costs of 𝑎𝑗aj along this path be 𝐴𝑖Ai. Then 𝑟𝑖ri is equal to the length of the maximum prefix of this path such that the sum of 𝑏𝑗bj along this prefix does not exceed 𝐴𝑖Ai.

Path Prefixes solution codeforcesExample for 𝑛=9n=9. The blue color shows the costs of 𝑎𝑗aj, and the red color shows the costs of 𝑏𝑗bj.
Consider an example. In this case:

  • 𝑟2=0r2=0, since the path to 22 has an amount of 𝑎𝑗aj equal to 55, only the prefix of this path of length 00 has a smaller or equal amount of 𝑏𝑗bj;
  • 𝑟3=3r3=3, since the path to 33 has an amount of 𝑎𝑗aj equal to 5+9+5=195+9+5=19, the prefix of length 33 of this path has a sum of 𝑏𝑗bj equal to 6+10+1=176+10+1=17 ( the number is 171917≤19);
  • 𝑟4=1r4=1, since the path to 44 has an amount of 𝑎𝑗aj equal to 5+9=145+9=14, the prefix of length 11 of this path has an amount of 𝑏𝑗bj equal to 66 (this is the longest suitable prefix, since the prefix of length 22 already has an amount of 𝑏𝑗bj equal to 6+10=166+10=16, which is more than 1414);
  • 𝑟5=2r5=2, since the path to 55 has an amount of 𝑎𝑗aj equal to 5+9+2=165+9+2=16, the prefix of length 22 of this path has a sum of 𝑏𝑗bj equal to 6+10=166+10=16 (this is the longest suitable prefix, since the prefix of length 33 already has an amount of 𝑏𝑗bj equal to 6+10+1=176+10+1=17, what is more than 1616);
  • 𝑟6=1r6=1, since the path up to 66 has an amount of 𝑎𝑗aj equal to 22, the prefix of length 11 of this path has an amount of 𝑏𝑗bj equal to 11;
  • 𝑟7=1r7=1, since the path to 77 has an amount of 𝑎𝑗aj equal to 5+3=85+3=8, the prefix of length 11 of this path has an amount of 𝑏𝑗bj equal to 66 (this is the longest suitable prefix, since the prefix of length 22 already has an amount of 𝑏𝑗bj equal to 6+3=96+3=9, which is more than 88);
  • 𝑟8=2r8=2, since the path up to 88 has an amount of 𝑎𝑗aj equal to 2+4=62+4=6, the prefix of length 22 of this path has an amount of 𝑏𝑗bj equal to 1+3=41+3=4;
  • 𝑟9=3r9=3, since the path to 99 has an amount of 𝑎𝑗aj equal to 2+4+1=72+4+1=7, the prefix of length 33 of this path has a sum of 𝑏𝑗bj equal to 1+3+3=71+3+3=7.

[Solution] Path Prefixes solution codeforces

The first line contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases in the test.

The descriptions of test cases follow.

Each description begins with a line that contains an integer 𝑛n (2𝑛21052≤n≤2⋅105) — the number of vertices in the tree.

This is followed by 𝑛1n−1 string, each of which contains three numbers 𝑝𝑗,𝑎𝑗,𝑏𝑗pj,aj,bj (1𝑝𝑗𝑛1≤pj≤n1𝑎𝑗,𝑏𝑗1091≤aj,bj≤109) — the ancestor of the vertex 𝑗j, the first and second values an edge that leads from 𝑝𝑗pj to 𝑗j. The value of 𝑗j runs through all values from 22 to 𝑛n inclusive. It is guaranteed that each set of input data has a correct hanged tree with a root at the vertex 11.

It is guaranteed that the sum of 𝑛n over all input test cases does not exceed 21052⋅105.

Output

For each test case, output 𝑛1n−1 integer in one line: 𝑟2,𝑟3,,𝑟𝑛r2,r3,…,rn.

Example
input

Copy
4
9
1 5 6
4 5 1
2 9 10
4 2 1
1 2 1
2 3 3
6 4 3
8 1 3
4
1 1 100
2 1 1
3 101 1
4
1 100 1
2 1 1
3 1 101
10
1 1 4
2 3 5
2 5 1
3 4 3
3 1 5
5 3 5
5 2 1
1 3 2
6 2 1
output

Copy
0 3 1 2 1 1 2 3 
0 0 3 
1 2 2 
0 1 2 1 1 2 2 1 1 

[Solution] Path Prefixes solution codeforces

The first example is parsed in the statement.

In the second example:

  • 𝑟2=0r2=0, since the path to 22 has an amount of 𝑎𝑗aj equal to 11, only the prefix of this path of length 00 has a smaller or equal amount of 𝑏𝑗bj;
  • 𝑟3=0r3=0, since the path to 33 has an amount of 𝑎𝑗aj equal to 1+1=21+1=2, the prefix of length 11 of this path has an amount of 𝑏𝑗bj equal to 100100 (100>2100>2);
  • 𝑟4=3r4=3, since the path to 44 has an amount of 𝑎𝑗aj equal to 1+1+101=1031+1+101=103, the prefix of length 33 of this path has an amount of 𝑏𝑗bj equal to 102102, .

For Solution

Click Here

Leave a Comment