410701: GYM104081 B 翻新道路 II
Description
在维斯特洛大陆上,有 $$$n$$$ 座城堡,共有 $$$n-1$$$ 条道路将这些城堡连接在一起,保证任意两个城堡之间都有且只有一条简单路径。这些道路因为年久失修,现在需要翻新。国王之手现在有一个计划清单,计划清单里包含若干个城堡的编号,他希望将计划清单中每对城堡之间的路径上的道路都翻新一下(同一条道路只会翻新一次)。如果一个城堡相邻的道路得到翻新或者这个城堡在清单中,城堡的领主将赞助 $$$a_i$$$ 元。现在,我们假定我们选定的城堡编号分别为$$$b_1,b_2,...,b_k$$$(对于任意的 $$$i<j,1\leq b_i<b_j\leq n$$$),那么收到的总赞助显然为$$$∑ a_{b_i}$$$。但是国王之手是一个很麻烦的人,他可能随时会改变计划:增加或删除清单里的城堡。
现在身为财政大臣的 YahAHa 被搞得焦头烂额,他想请你帮他算一算,每次国王之手改变计划后,将预计收到的领主们的赞助的总和。
Input第一行包含一个整数 $$$T$$$ $$$(1\le T \le 10^5)$$$,表示测试用例的个数。
每个测试用例的第一行包含三个整数 $$$n$$$,$$$m(m \le n)$$$,$$$q$$$,分别表示城堡的个数,起始时清单城堡的个数以及操作次数。
第二行,包含$$$n$$$个整数,表示第$$$i$$$个城堡领主将赞助 $$$a_i(1 \le a_i \le 10^9)$$$ 元。
第 $$$3$$$ 到第 $$$n+1$$$ 行,每行有两个整数 $$$u$$$,$$$v$$$,代表城堡 $$$u$$$ 和城堡 $$$v$$$ 存在一条道路。
第 $$$n+2$$$ 行,包含 $$$m$$$ 个整数,表示起始时清单里的城堡(保证 $$$m$$$ 个整数互不相同)。
第 $$$n+3$$$ 到第 $$$n+q+2$$$ 行,每行描述一个操作,其格式为:$$$op$$$ $$$u$$$
当 $$$op=1$$$ 时,表示将城堡 $$$u$$$ 加入清单,保证 $$$u$$$ 之前一定不在清单中。
当 $$$op=2$$$ 时,表示将城堡 $$$u$$$ 从清单中删除,保证 $$$u$$$ 之前一定在清单中。
保证对于所有用例 $$$\displaystyle\sum{n} \le 10^5$$$ , $$$ \displaystyle\sum{q} \le 10^5$$$ 。
Output对于每次操作,输出一行一个整数表示操作之后将收到多少赞助费。
ExampleInput1 5 2 2 1 2 3 4 5 2 1 2 3 2 4 2 5 1 3 1 4 1 5Output
10 15Note
对于第一次操作之后,清单有 $$$1、3、4$$$ 号城堡, $$$1、2、3、4$$$ 号城堡将提供赞助费。