#P18934. [2026多校联测]救援

[2026多校联测]救援

救援

题目描述

A 国形如一棵有根树,其中 11 号城市是 A 国的首都,其它每个城市都有其上属城市。具体的,第 ii 个城市到其上属城市为 faifa_i 有一条道路,这条道路的长度为 wiw_i。

我们称一个城市 yy 是城市 xx 的间接附属,当且仅当城市 yy 的上属城市 fayfa_y 是城市 xx,或者城市 fayfa_y 是城市 xx 的间接附属。定义 dist(x,y)\mathrm{dist}(x,y) 表示从城市 xx 到城市 yy 的最短路径长度。

由于 A 国天灾频发,各城市消防安全部队需要联合救援。定义城市 ii 消防安全部队的工作量为 aia_i,当城市 ii 消防安全部队前往城市 xx 执行一次任务时,工作量会增加 dist(i,x)\mathrm{dist}(i,x),即 ai←ai+dist(i,x)a_i\leftarrow a_i+\mathrm{dist}(i,x)。每个城市的初始工作量是 00。

中央指挥部总共发出了 qq 条指令:

  • 1 x y1\ x \ y:执行任务:城市 yy 发生了一场灾难,命令城市 xx 及其所有间接附属的城市的消防安全部队前往城市 yy 前线支援,执行一次到城市 yy 的任务;
  • 2 x2\ x:查询工作量:查询城市 xx 及其所有间接附属的城市的消防安全部队工作量的总和。

输入格式

第一行给定两个整数 n,qn,q,分别表示城市数量和指令数量。

接下来 n−1n-1 行,第 ii 行给定两个整数 fai+1,wi+1fa_{i+1},w_{i+1},分别表示城市 i+1i+1 的上属城市以及路径长度。

接下来 qq 行,每行形如:

  • 1 x y1\ x \ y:表示第一类指令:执行任务。
  • 2 x2\ x:表示第二类指令:查询工作量。

输出格式

对于每条第二类指令,输出一行一个整数,表示总工作量。

样例 1 输入

5 4
1 3
1 2
2 1
2 2
1 5 1
2 1
1 2 3
2 2

样例 1 输出

5
23

样例 2

见选手目录下的 rescue2.in 与 rescue2.ans。

样例 3

见选手目录下的 rescue3.in 与 rescue3.ans。

样例 4

见选手目录下的 rescue4.in 与 rescue4.ans。

样例 5

见选手目录下的 rescue5.in 与 rescue5.ans。

数据范围

对于所有测试数据,保证:

  • 1≤n,q≤5×1051\le n,q\le 5\times 10^5
  • 1≤fai+1<i+11\le fa_{i+1}<i+1
  • 1≤wi+1≤1001\le w_{i+1}\le 100
  • 1≤x,y≤n1 \le x,y \le n
测试点编号 n,q≤n,q\le 特殊性质
1,21,2 2020 无
3∼53\sim 5 20002000
6,76,7 5×1055 \times 10^5 A
8,98,9 ^ B
10∼1310\sim 13 C
14∼2014\sim 20 无
  • 特殊性质 A:对于所有 1<i≤n1 < i \le n,fai=i−1fa_i = i-1。
  • 特殊性质 B:对于所有 1<i≤n1 < i \le n,fai=1fa_i = 1。
  • 特殊性质 C:对于所有第一类指令,保证 x=1x=1。