Description

Given a rooted tree with $n$ nodes and weighted edges. Nodes are numbered from $1$ to $n$, and node $1$ is the root.

Given a parameter $t$, for each node $u$, find how many nodes in the subtree of $u$ have distance to $u$ not greater than $t$.

Input Format

The first line contains two integers, the number of nodes $n$ and the parameter $t$.

For each $i$ from $2$ to $n$, the $i$-th line contains two integers $p_i, w_i$, meaning the parent of node $i$ is $p_i$, and the weight of the edge connecting $i$ and $p_i$ is $w_i$.

Output Format

Output $n$ lines. The $i$-th line contains an integer, the number of nodes in the subtree of $i$ whose distance to $i$ is at most $t$.

4 5 
1 4 
2 3 
1 5 

3 
2 
1 
1 

Hint

Constraints

• $1 \leq n \leq 2 \times 10^5$, $1 \leq t \leq 10^{18}$.
• $1 \leq p_i \lt i$, $1 \leq w_i \leq 10^{12}$.

Translated by ChatGPT 5