P10574 [JRKSJ R8] 暴风雪
题目背景
题目描述
层叠都市可以被抽象为一棵树。于是给你一棵带点权 $v_i$ 的树，树以 $1$ 为根。初始点权 $v_i$ 均为 $0$。
定义 $\text{dis}(x,y)$ 为树上 $x,y$ 之间的距离，即 $x\to y$ 的简单路径上的边数。
设 $\text{subtree}(x)$ 为树上以 $x$ 为根的子树，定义 $f(x)=\max_{d\ge 0} \sum_{y\in\text{subtree}(x)} v_y[\text{dis}(x,y)=d]$。也就是说，$f(x)$ 表示 $x$ 子树中的每一层的点权和的最大值。
现在给出 $m$ 次操作，每次操作中给出 $x,w,y$，先令 $v_x\gets v_x+w$，然后求 $\sum_{i\in \text{subtree}(y)} f(i)$。
输入格式
无
输出格式
无
说明/提示
### 数据规模与约定
**本题采用捆绑测试。**
| $\text{Subtask}$ | $n,m\le$ | 特殊性质 | $\text{Score}$ | 时间限制|
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $100$ | | $5$ | 1s |
| $2$ | $5000$ | | $15$ | 1s |
| $3$ | $3\times10^5$ | $f_i=i-1$ | $10$ | 4.5s |
| $4$ | $7\times 10^4$ | | $20$ | 4.5s |
| $5$ | $3\times10^5$ | | $50$ | 4.5s |
对于所有数据，$1\le n,m\le3\times 10^5$，$1\le x,y\le n$，$1\le w \le 10^8$，$1\le f_i\le n$。