题目来自第 43 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 8.0 秒

空间限制： 512 MB

题目描述

1346 有一棵大小为 $n$ 的圣诞树，树上的每个节点有一盏灯，节点 $i$ 上的灯的颜色为 $c_i$。任意时刻，每盏灯的状态为开着或关着两种之一。

初始时，所有灯的状态可以用一个长为 $n$ 的 $01$ 串 $s$ 表示。对于节点 $i$ 上的灯，如果 $s_i = 0$，表示这盏灯初始时是关着的；否则表示这盏灯初始时是开着的。

树的所有边可以用 $n - 1$ 个三元组表示，第 $i$ 个三元组 $(u_i, v_i, w_i)$ 表示节点 $u_i$ 与节点 $v_i$ 之间有一条长度为 $w_i$ 的边。

定义一条从 $u$ 到 $v$ 的路径是好看的，当且仅当以下三个条件同时满足：

• 节点 $u$ 和节点 $v$ 上的灯都是亮着的；
• $u$ 到 $v$ 的路径长度为 $k$ 的倍数；
• 有且仅有一种颜色，满足 $u$ 到 $v$ 的路径上有奇数个这种颜色的灯。这里灯颜色的出现次数与对应灯是否开启无关。

1346 好奇，对于这样的一棵树，有多少个无序二元组 $\{u, v\}$，满足 $u$ 到 $v$ 的路径是好看的。其中 $u$ 和 $v$ 可以相同。

当然，1346 有些时候也会更改一盏灯的状态（把开着的变成关着的，把关着的变成开着的）。1346 也想知道，在每次修改过后，有多少个无序二元组 $\{u, v\}$，满足 $u$ 到 $v$ 的路径是好看的。

输入格式

从标准输入读入数据。

第一行输入四个整数 $n, m, k, q$，依次表示树的大小，颜色种类数，“好看的”路径长度参数，更改次数。

接下来一行输入一个长为 $n$ 的 $01$ 串 $s$，表示初始时灯的状态。

接下来一行输入 $n$ 个正整数 $c_1, c_2, \dots, c_n$，表示每盏灯的颜色。

接下来 $n - 1$ 行，每行输入三个正整数 $u, v, w$，表示节点 $u$ 和 $v$ 之间有一条长度为 $w$ 的边。

接下来 $q$ 行，每行输入一个正整数 $u$，表示更改节点 $u$ 上的灯的状态。

输出格式

输出到标准输出。

输出 $q + 1$ 行，每行一个非负整数。

其中第 $1$ 行表示初始树上有多少对满足条件的无序二元组；

接下来的 $q$ 行中，第 $i$ 行表示第 $i$ 次修改之后，树上有多少对满足条件的无序二元组。

5 3 4 5
01101
1 2 2 2 1
3 1 580377
3 2 900057
3 5 49869
3 4 868795
1
1
3
4
5

3
4
3
2
5
3

样例 1 解释

初始时，只有点对 $\{2, 2\}, \{3, 3\}$ 和 $\{5, 5\}$ 合法，共 $3$ 个。

修改点 $1$ 上的灯的状态为开后，点对 $\{1, 1\}, \{2, 2\}, \{3, 3\}$ 和 $\{5, 5\}$ 合法，共 $4$ 个。

修改点 $1$ 上的灯的状态为关后，点对 $\{2, 2\}, \{3, 3\}$ 和 $\{5, 5\}$ 合法，共 $3$ 个。

修改点 $3$ 上的灯的状态为关后，点对 $\{2, 2\}$ 和 $\{5, 5\}$ 合法，共 $2$ 个。

修改点 $4$ 上的灯的状态为开后：

• 点对 $\{2, 2\}, \{4, 4\}$ 和 $\{5, 5\}$ 合法。
• 点 $2$ 到点 $4$ 的路径上，颜色 $1$ 的灯有 $0$ 个，颜色 $2$ 的灯有 $3$ 个，有且仅有颜色 $2$ 出现了奇数次；路径长度为 $900057 + 868795 = 1768852$，是 $k = 4$ 的倍数；所以点对 $\{2, 4\}$ 合法；
• 点 $4$ 到点 $5$ 的路径上，颜色 $1$ 的灯有 $1$ 个，颜色 $2$ 的灯有 $2$ 个，有且仅有颜色 $1$ 出现了奇数次；路径长度为 $868795 + 49869 = 918664$，是 $k = 4$ 的倍数；所以点对 $\{4, 5\}$ 合法。

共 $5$ 对点对。

修改点 $5$ 上的灯状态为关后，点对 $\{2, 2\}, \{2, 4\}$ 和 $\{4, 4\}$ 合法，共 $3$ 个。

样例 2

见题目文件区的 2.in 和 2.ans。

样例 2 解释

该样例满足测试点 $1 \sim 3$ 的限制条件。

样例 3

见题目文件区的 3.in 和 3.ans。

样例 3 解释

该样例满足测试点 $4 \sim 6$ 的限制条件。

样例 4

见题目文件区的 4.in 和 4.ans。

样例 4 解释

该样例满足测试点 $7 \sim 10$ 的限制条件。

样例 5

见题目文件区的 5.in 和 5.ans。

样例 5 解释

该样例满足测试点 $11 \sim 14$ 的限制条件。

样例 6

见题目文件区的 6.in 和 6.ans。

样例 6 解释

该样例满足测试点 $15 \sim 20$ 的限制条件。

子任务

对于 $100\%$ 的数据，满足 $n \le 10^5, m \le 40, k \le 4, q \le 10^5, 1 \le c_i \le m, 1 \le u_i, v_i \le n, 1 \le w_i \le 10^6$。

测试点编号	$n \le$	$m \le$	$k \le$	$q \le$
$1 \sim 3$	$2 \times 10^{3}$	$40$	$4$	$2 \times 10^{3}$
$4 \sim 6$	$10^{5}$	$1$		$10^{5}$
$7 \sim 10$		$40$	$1$
$11 \sim 14$			$4$	$1$
$15 \sim 20$				$10^{5}$