P3066 [USACO12DEC] Running Away From the Barn G

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$.

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 $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$.

#### 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