#P17771. 树上的毒瘤

树上的毒瘤

题目描述

这棵树上有 nn 个节点,由 n−1n-1 条树枝相连。初始时树上都挂了一个毒瘤,颜色为 cic_i。接下来 Salamander 将会进行 qq 个操作。

Salamander 有时会修改树上某个点到另外一个点的简单路径上所有毒瘤的颜色。

对于给定的树上某个点集 S\bm{S},Salamander 还定义了某个点的权值:

Wi=∑j∈ST(i,j)W_i=\sum_{j\in S}T(i,j)

其中 T(i,j)T(i,j) 表示 ii 到 jj 的路径上毒瘤颜色的段数,比如 ii 到 jj 的路径上毒瘤颜色为 12233121223312 时,颜色段数为 55。

Salamander 对树上的毒瘤们的状态很感兴趣,所以有时会指定树上 mm 个节点作为点集,询问这 mm 个节点的权值。

输入格式

第一行包括两个正整数 nn、qq,表示树上的节点数和操作个数。

第二行包括用空格隔开的 nn 个正整数 cic_i,表示树上每个节点初始的毒瘤颜色。

接下来 n−1n-1 行,每行两个正整数 uu、vv,表示树上有一条连接 uu 和 vv 的边。

接下来描述 qq 个操作:

  1. 若给出的第一个整数等于 11,那么接下来将会有三个正整数 uu、vv、yy,表示将树上编号为 uu 的点到编号为 vv 的点的简单路径上的毒瘤颜色全都改为 yy。

  2. 若给出的第一个整数等于 22,那么接下来将会有一个正整数 mm,表示指定的树上节点个数。下一行将会有 mm 个用空格隔开的互不相同的正整数,表示当前询问给定的 mm 个节点。

输出格式

若干行,对于每个 22 操作输出对应的答案。

输入输出样例 #1

输入 #1

10 10
708916891 100649777 100649777 544409200 100649777 47435517 47435517 708916891 644811607 544409200 
3 2
7 1
8 1
1 10
3 4
1 5
9 2
1 2
3 6
2 1
6 
2 6
8 10 9 3 2 4 
2 2
7 8 
2 1
5 
2 2
6 10 
2 3
6 1 4 
2 1
7 
1 9 8 100649777
1 7 9 544409200
2 4
10 9 1 2 

输出 #1

1 
13 17 15 11 11 15 
3 3 
1 
5 5 
7 7 7 
1 
4 4 4 4 

说明/提示

保证输入数据合法。

对于 30%30\% 的数据,有 1≤n,q≤10001\leq n,q\leq 1000,∑m≤5000\sum m\leq 5000。

对于 60%60\% 的数据,有 1≤n,q≤200001\leq n,q\leq 20000,∑m≤100000\sum m\leq 100000。

对于 100%100\% 的数据,有 1≤n,q≤1000001\leq n,q\leq 100000,ci,y≤109c_i,y\leq 10^9,∑m≤200000\sum m\leq 200000,m≤nm\leq n。