Migrated from Lutece 2941 Keep the least!!!

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag:dfs序+LCA+一些结论
给定一棵$n$个点的树，树上点的编号从$1$到$n$，每个点$i$都有点权$a_i$。对于一个点集$S$，点集$T$总是满足：

1. $S$是$T$的子集；
2. 对于树上的边$(u,v)$，若只保留满足u$\in$T且v$\in$T的边而删除其余所有边，能使得S集合所有点在同一个连通块中。

给定一个初始的点集$S$，包含$m$个点。现在进行$q$次操作，可分为两种操作：

1. 增加操作：向点集$S$中加入一个点$u$，保证$u$在此次操作前不在点集$S$中；
2. 删除操作：删除点集$S$中的一个点$u$，保证$u$在此次操作前存在于点集$S$中。

定义一个点集的权值是点集中所有点的权值之和。对于一个确定的点集$S$，总是存在一个或多个权值最小的点集$T$，请求出每次操作后$T$的最小权值。

Input

输入第一行包含三个整数$n,m,q$，分别表示点的个数、初始点集$S$的大小和操作次数。 输入第二行包含$n$个整数，其中第$i$个整数表示第$i$个点的点权$a_i$。 接下来$n-1$行，每行包含两个正整数$u$和$v$，表示点$u$和点$v$之间存在一条边。 接下来一行包含$m$个整数，表示初始$S$集合中包含的点的编号。 接下来$q$行，每行描述一次操作，包含两个正整数$opt$和$u$：

1. 若$opt=1$，则表示向$S$中加入点$u$。
2. 若$opt=2$，则表示删除$S$中的点$u$。

保证所有操作合法。

Output

对于每次操作，输出一行一个整数，表示此时$T$的最小权值。

Samples

7 2 5
5 2 1 1 3 1 4
1 2
2 3
2 4
4 5
5 6
6 7
6 7
1 1
1 2
1 3
2 6
2 7

16
16
17
17
8

Constraints

$1\le n,m,q\le 10^5,1\le m\le n,1\le u,v\le n,1\le a_i\le 10^9,opt=1,2$

Resources

2023 UESTC ICPC Training for Data Structures