题目描述

Chef declared war on Byteland. Chefs best scientist Pramod has designed a new Fighter Plane which can fly with Speed of Light!! So none of the defence forces of Byteland can defeat or defend it.

Byteland has a structure of a tree with $N$ cities connected by $N-1$ bidirectional roads. Each city has index between $[1,n]$ (inclusive) and no two cities have same index. The capital city of Byteland has index $1$. The distance between two cities is the number of roads in the path from one to other.

If the plane drops a bomb on a city $A$, with damage value $X$ then the damage done to a city $B$ will be $\lfloor \frac{X}{2^d}\rfloor$ where $d$ is the distance between $A$ and $B$, note that as the distance of $A$ from itself is $0$, the damage done to $A$ will be $\lfloor \frac{X}{2^0}\rfloor = X$.

Each city has a certain wealth $W_i$ in it, if it is damaged by a value of $X$ then its wealth is reduced by $X$. On a day if the wealth of a city becomes less than or equal to zero then it is considered Economically Dead.

Your task is to write a program that keeps track of the bombings done by the plane and answer the queries asked by the chef. The chef has a total of $Q$ queries for you. There are two types of queries.

  1. Chef gives you two integers $A$ and $X$, which means that the plane drops a bomb on the city with index $A$ with damage value $X$. A bomb can also be dropped on economically dead city.
  2. Chef gives you an integer $A$ and you need to print the number of cities that are economically dead which have $A$ in the path from the capital to them.
    (See explanation for better understanding)

Constraints

$1 \leq N \leq 10^5$

$1 \leq Q \leq 10^5$

$1 \leq X \leq 10^5$

$1 \leq W_i \leq 10^9$

思路

观察数据范围,发现每次修改的影响范围 $\log X$ 最大不超过 $15$,我们可以猜想算法复杂度和 $\log X$ 相关。

对于更新,考虑到一个子树内深度相同的点在 BFS 序上是连续的一段,我们可以在 BFS 序上建线段树,维护区间的权值最小值。对于每个受影响的深度,直接修改。

因为仍有 $\log X$ 个祖先是受影响的,在更新时应当注意把重复计算的权值消除。

对于查询,考虑一个子树内所有点在 DFS 序上是连续的一段,在 DFS 序上建树状数组,每次更新时遇到权值小于等于 $0$ 的新点就加入树状数组。

那么这道题就非常符合直觉地做完了。

代码