5221：Occupation

题目描述

Miceren finds a huge country named HY. HY has $N$ cities numbered from 1 to $N$ connected by $N~-~1$ bidirectional roads. There exists a path between any two cities.

It can be imagined as a tree with $n$ vertices rooted at vertex 1.

Miceren wants to occupy some cities here. Each city has a value $v_i$. (Notice that the value of a city may be negative. Nevertheless, Miceren wants to occupied this city.)

As some usual stories, someone named Cloud wants to "steal" some cities from Miceren.

At the beginning, Miceren and Cloud don't occupy any city.

In the following $Q$ days, one of three events may happen

1. Miceren will walk from the a-th city to the b-th city and all cities visited in this trip will belong to Miceren. ($1~\le~a, b~\le~N$)

2. Cloud will steal the x-th city. If Miceren occupied the x-th city before, Miceren will lost the control of this city. ($1~\le~x~\le~N$)

3. Miceren will occupy the subtree rooted at x.($1~\le~x~\le~N$)

As Miceren's friend, you must tell Miceren the total value of all cities which belong to Miceren after each day.

输入解释

The first line contains a single integer $T$, indicating the number of test cases.

Each test case begin with one integer $N$, indicating the number of cities in HY.

The next line contains $N$ integer $V_i$, indicating the value of each city.

The next $N~-~1$ lines contain the details of the roads. Each line contains two integers $u,~v$ meaning that there is a road between cities $u$ and $v$.

The next line contains one integer $Q$.

The next $Q$ lines contain the details of event. If the format is "1 a b", it means the first event happened where Miceren walks from a-th city to b-th city. If the format is “2 x”, it means the second event happened where Cloud "steal"s the x-th city. Otherwise the format is “3 x” and the third event happened where Micron occupied the subtree rooted at x.

$T$ is about 100.

$1~\le~N, Q~\le~100000.$

$-1000~\le~V_i~\le~1000.$

The ratio of test cases with $N~\gt~100$ is less than 5%.

输出解释

For each test queries, print the answer.

输入样例

1
10
1 2 3 4 5 6 7 8 9 10 
1 2
1 3
2 4
2 5
5 9
5 10
3 6
3 7
3 8
6
1 10 4
1 9 7
2 5
3 4
2 4
1 6 10

输出样例

提示

If you need a larger stack size, 
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

来自杭电HDUOJ的附加信息

Recommend

hujie

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源赛码"BestCoder"杯中国大学生程序设计冠军赛

源链接： HDU-5221

最后修改于 2020-10-25T23:20:49+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
12000/6000MS(Java/Others)	131072/131072K(Java/Others)