P11408 [RMI 2020] 树咖 / Arboras

译自 [8th Romanian Master of Informatics, RMI 2020](https://rmi.lbi.ro/rmi_2020/) D2T3。$\texttt{3s,0.25G}$。

有一棵 $N$ 个节点的有根树，边有边权。节点编号为 $0\sim N-1$，$0$ 号点为根。 定义 $f(u)$ 为 $u$ 子树内经过 $u$ 的最长链的长度。 $Q$ 次操作，一次操作将一条边的边权**加上一个正数**。在第一次操作前，和每次操作后，求出 $\displaystyle \left(\sum_{1\le i\le N} f(i)\right)\bmod (10^9+7)$。

第一行，一个正整数 $N$。 第二行，$(N-1)$ 个整数 $p_1,\cdots,p_{N-1}$，$p_i$ 表示 $i$ 号点的父亲为 $p_i$。 第三行，$(N-1)$ 个正整数 $d_1,\cdots,d_{N-1}$，$d_i$ 表示 $(i,p_i)$ 边边权为 $d_i$。 第四行，一个正整数 $Q$。 接下来 $Q$ 行，每行两个正整数 $x,v$，表示给 $(x,p_x)$ 边权增加 $v$。

输出 $(Q+1)$ 行，每行一个整数： - 第一行，输出第一次操作前的答案。 - 接下来 $Q$ 行，输出每次操作后的答案。

对于 $100\%$ 的数据，保证： - $1\le N,Q\le 10^5$； - $1\le d_i\le 10^9$； - $0\le p_i\lt i$； - $1\le v\le 10^9$； - $1\le x\lt N$。 | 子任务编号 | $N,Q\le$ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 10^3 $ | | $11$ | | $ 2 $ | $ 10^5 $ | A | $13$ | | $ 3 $ | $ 10^5 $ | B | $31$ | | $ 4 $ | $ 10^5 $ | | $45$ | - 特殊性质 A：树高不大于 $50$； - 特殊性质 B：$d_i=10^9$，$v=1$。