P4242 树上的毒瘤

题目背景

Salamander开心地把一大袋毒瘤带回了家,把他们染上了不同的颜色,并把他们挂在了院子里的树上。

题目描述

这棵树上有$n$个节点,由$n-1$条树枝相连。初始时树上都挂了一个毒瘤,颜色为$c_i$。接下来Salamander将会进行$q$个操作。 Salamander有时会修改树上某个点到另外一个点的简单路径上所有毒瘤的颜色。 对于给定的树上**某个点集$S$**,Salamander还定义了某个点的权值: $$W_i=\sum_{j\in S}T(i,j)$$ 其中$T(i,j)$表示$i$到$j$的路径上毒瘤颜色的**段数**,比如$i$到$j$的路径上毒瘤颜色为$1223312$时,颜色段数为$5$。 Salamander对树上的毒瘤们的状态很感兴趣,所以有时会指定树上$m$个节点作为点集,询问这$m$个节点的权值。

输入格式

输出格式

说明/提示

保证输入数据合法。 对于30%的数据,有$1\leq n,q\leq 1000$,$\sum m\leq 5000$。 对于60%的数据,有$1\leq n,q\leq 20000$,$\sum m\leq 100000$。 对于100%的数据,有$1\leq n,q\leq 100000$,$c_i,y\leq 10^9$,$\sum m\leq 200000$,$m\leq n$。