P14588 [LNCPC 2025] 前线支援

A 国风景秀丽，由 $n$ 个城市组成，每个城市都别具一格，形成了丰富多彩的大国江山。不过遗憾的是，受金融危机的影响，A 国财政紧张，所以仅有 $n-1$ 条双向道路连接着这 $n$ 座城市。为了保证城市的方便快捷，这 $n-1$ 条道路能保证一定能从一座城市到达另一座城市。 A 国城市制度井然有序：其中 $1$ 号城市是 A 国的首都，其它每个城市都有其上属城市。具体而已对于第 $i$ 个城市到其上属城市为 $fa_i$（$1\le fa_i

第一行给定两个整数 $n,q(1\le n,q\le 5\times 10^5)$，分别表示城市数量和指令数量。 接下来 $n-1$ 行，每行给定两个整数 $fa_{i+1},w_{i+1}(1\le fa_{i+1}

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