Heavy‐Light Partition on a Weighted Rooted Tree

Given a rooted weighted tree with n nodes numbered from \(1\) to \(n\) (with node 1 being the root), where each edge has a positive integer weight, you are to perform a special partition of the tree. For each node, you can choose an arbitrary subset (possibly empty or all) of its children to be heavy children. The edge connecting a parent to a heavy child is called a heavy edge; all other edges are called light edges.

For a fixed nonnegative integer \(i\), a partition is called \(i\)-heavy if every node has at most \(i\) heavy children. In addition, for a fixed nonnegative integer \(j\), a partition is called \(j\)-light if for every simple path from the root (node 1) to any node, the sum of the weights of light edges along the path does not exceed \(j\).

Your task is: for every \(i=0,1,\dots,n-1\), determine the minimum \(j\) for which there exists an \(i\)-heavy partition that is also \(j\)-light.

The formulas used in the problem statement are in \( \LaTeX \) format.

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), the number of nodes in the tree. The following \(n-1\) lines describe the tree. For each node \(2 \leq i \leq n\), a line contains two integers \(p\) and \(w\) indicating that there is an edge from node \(p\) (the parent) to node \(i\) with weight \(w\) (\(1 \leq w \leq 10^9\)). It is guaranteed that the given graph is a tree with node 1 as the root.

outputFormat

Output \(n\) space‐separated integers. The \(i\)th integer (starting from \(i=0\)) should be the minimum \(j\) such that there exists an \(i\)-heavy partition that is \(j\)-light.

sample

1

0