思路总览

核心目标：在动态切换红点的同时，高效回答“到所有红点距离之和”。直接维护会超时，因此使用点分治配合分层距离与分组前缀量维护。

关键记号

• 用点分治把树分成若干层重心。对每个原树节点 $u$，记录它到每一层重心的距离序列：

  

题目内容

给定一棵以节点 $1$ 为根的树，树上共有 $n$ 个节点，其中某些节点被标记为"红点"。每条边 $(u,v)$ 具有正整数权重 $w_{uv}$ 。

接下来有 $q$ 次操作，每次操作有两种类型：

1.切换节点 $v$ 的红点状态(若为红点则变为非红点，反之亦然)

2.查询节点 $v$ 到所有当前红点的带权距离之和 $S_v$ 。

请对所有查询操作输出对应结果。

【名词解释】：

• 带权距离：带权距离 指路径上所有边权的总和。

输入描述

第一行输入两个整数 $n,q(1 ≤ n,q≦ 2 ×10^5)$ ，分别表示节点数和操作数。

第二行输入 $n$ 个整数 $c_1,c_2,…,c_n ∈$ {$0,1$} ，其中 $c_i = 1$ 表示第 $i$ 个节点初始为红点，$c_i=0$ 表示非红点。

接下来 $n -1$ 行，每行输入三个整数 $u_i,v_i,w_i(1≤u_i,u_i≦n, u_i≠v_i,1≤w_i≤10^6)$ ，表示一条无向带权边。

随后 $q$ 行，每行输入两个整数 $t$ 和 $v(t ∈$ {$1,2$} $,1 ≦u≦ n)$，表示一次操作。

保证所有输入的边构成一棵树，并且至少存在一个操作 $2$ 。

输出描述

对于每个操作类型 $2$ ，输出一行整数，表示节点 $v$ 到所有当前红点的带权距离之和 $S_v$ 。

样例1

输入

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

输出

8
11
8
8

说明

在这个样例中：

初始红点为 {$1,3,5$} ;

操作 $2$ $1$ ：$S_1=0+2+6=8$ ；

操作 $2$ $2$ ：$S_2=1+3+7= 11$ ；

操作 $1$ $3$ ：切换节点 $3$ 为非红点，红点变为 {$1,5$} ；

操作 $2$ $2$ ：$S_2=1+7=8$ ；

操作 $2$ $2$ ：红点不变，$S_2 = 8$ 。