GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Tuesday 2 August 2022

[Solution] Path Prefixes Codeforces Solution


G. Path Prefixes
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a rooted tree. It contains n vertices, which are numbered from 1 to n. The root is the vertex 1.

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

Output n1 numbers r2,r3,,rn, where ri is defined as follows.

Consider the path from the root (vertex 1) to i (2in). 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.

Example for n=9. The blue color shows the costs of aj, and the red color shows the costs of bj.

Consider an example. In this case:

  • r2=0, since the path to 2 has an amount of aj equal to 5, only the prefix of this path of length 0 has a smaller or equal amount of bj;
  • r3=3, since the path to 3 has an amount
Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied


  •  of aj equal to 5+9+5=19, the prefix of length 3 of this path has a sum of bj equal to 6+10+1=17 ( the number is 1719);
  • r4=1, since the path to 4 has an amount of aj equal to 5+9=14, the prefix of length 1 of this path has an amount of bj equal to 6 (this is the longest suitable prefix, since the prefix of length 2 already has an amount of bj equal to 6+10=16, which is more than 14);
  • r5=2, since the path to 5 has an amount of aj equal to 5+9+2=16, the prefix of length 2 of this path has a sum of bj equal to 6+10=16 (this is the longest suitable prefix, since the prefix of length 3 already has an amount of bj equal to 6+10+1=17, what is more than 16);
  • r6=1, since the path up to 6 has an amount of aj equal to 2, the prefix of length 1 of this path has an amount of bj equal to 1;
  • r7=1, since the path to 7 has an amount of aj equal to 5+3=8, the prefix of length 1 of this path has an amount of bj equal to 6 (this is the longest suitable prefix, since the prefix of length 2 already has an amount of bj equal to 6+3=9, which is more than 8);
  • r8=2, since the path up to 8 has an amount of aj equal to 2+4=6, the prefix of length 2 of this path has an amount of bj equal to 1+3=4;
  • r9=3, since the path to 9 has an amount of aj equal to 2+4+1=7, the prefix of length 3 of this path has a sum of bj equal to 1+3+3=7.
Input

The first line contains an integer t (1t104) — 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 (2n2105) — the number of vertices in the tree.

This is followed by n1 string, each of which contains three numbers pj,aj,bj (1pjn1aj,bj109) — 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 2 to n inclusive. It is guaranteed that each set of input data has a correct hanged tree with a root at the vertex 1.

It is guaranteed that the sum of n over all input test cases does not exceed 2105.

Output

For each test case, output n1 integer in one line: r2,r3,,rn.

No comments:

Post a Comment