P3261 [JLOI2015] City Conquest

Xiao Mingming recently got a new board game. In the game, you need to use $m$ knights to conquer $n$ cities. The $n$ cities are numbered from $1$ to $n$. Except for city $1$, each city $i$ is governed by another city $f_i$ with $f_i

The first line contains two positive integers $n,m$, the numbers of cities and knights. The second line contains $n$ integers, where the $i$-th number is $h_i$, the defense value of city $i$. Lines $3$ to $n+1$: for each city $i$ from $2$ to $n$, line $i+1$ contains three integers $f_i,a_i,v_i$, denoting the governing (parent) city of city $i$ and the two combat-power change parameters. Lines $n+2$ to $n+m+1$: for each knight $i$ from $1$ to $m$, line $n+1+i$ contains two integers $s_i,c_i$, the initial combat power and the first city to attack.

Output $n+m$ lines, each containing a nonnegative integer. The first $n$ lines give, for cities $1$ to $n$, the number of knights who die there; the last $m$ lines give, for knights $1$ to $m$, the number of cities they capture.

For $100\%$ of the testdata, $1\le n,m\le 3\times 10^5$, $-10^{18}\le h_i,v_i,s_i\le 10^{18}$, $1\le f_i0$, and that at any time the absolute value of a knight's combat power does not exceed $10^{18}$. Translated by ChatGPT 5