{"raw_statement":[{"iden":"background","content":"![]( https://cdn.luogu.com.cn/upload/image_hosting/ok3qwkac.png)"},{"iden":"statement","content":"层叠都市可以被抽象为一棵树。于是给你一棵带点权 $v_i$ 的树，树以 $1$ 为根。初始点权 $v_i$ 均为 $0$。\n\n定义 $\\text{dis}(x,y)$ 为树上 $x,y$ 之间的距离，即 $x\\to y$ 的简单路径上的边数。\n\n设 $\\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$ 子树中的每一层的点权和的最大值。\n\n现在给出 $m$ 次操作，每次操作中给出 $x,w,y$，先令 $v_x\\gets v_x+w$，然后求 $\\sum_{i\\in \\text{subtree}(y)} f(i)$。"},{"iden":"input","content":"第一行两个整数 $n,m$。\n\n第二行 $n-1$ 个整数 $f_{2\\dots n}$，依次表示结点 $2,3,\\dots ,n$ 的父亲。\n\n接下来 $m$ 行，每行三个整数 $x,w,y$。"},{"iden":"output","content":"输出共 $m$ 行，每行一个整数表示答案。"},{"iden":"note","content":"### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n| $\\text{Subtask}$ | $n,m\\le$ |  特殊性质 |  $\\text{Score}$ | 时间限制|\n| :----------: | :----------: | :----------: | :----------: |  :----------: |  \n| $1$ | $100$ |  | $5$ | 1s |\n| $2$ | $5000$ |  | $15$ | 1s |\n| $3$ | $3\\times10^5$ | $f_i=i-1$ | $10$ | 4.5s |\n| $4$ | $7\\times 10^4$ |  | $20$ | 4.5s |\n| $5$ | $3\\times10^5$ |  | $50$ | 4.5s |\n\n对于所有数据，$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$。"}],"translated_statement":null,"sample_group":[["5 7\n1 1 1 4\n2 1 5\n4 2 1\n3 4 1\n2 5 5\n2 4 5\n4 4 4\n3 2 2","0\n6\n14\n0\n0\n6\n10"],["6 10\n1 1 1 1 2\n6 4 1\n3 1 1\n1 1 1\n3 4 1\n5 2 1\n3 3 1\n3 4 1\n2 2 1\n2 5 1\n3 1 1","12\n13\n13\n18\n22\n28\n36\n38\n46\n48"],["8 10\n1 1 2 1 3 3 3\n7 3 1\n2 4 1\n5 2 1\n5 2 1\n3 1 1\n6 2 1\n1 4 1\n8 4 1\n6 4 1\n3 2 1","9\n14\n18\n22\n23\n27\n27\n35\n47\n47"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}