标记子树实现的一个道路算法问题,怎么采用C语言的程序代码编写设计的实现?

Problem Description
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 vi. (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 ≤ a,b ≤ 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 ≤ x ≤ N)

  3. Miceren will occupy the subtree rooted at x.(1 ≤ x ≤ N)

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

Input
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 Vi, 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 ≤ N,Q ≤ 100000.

−1000 ≤ Vi ≤ 1000.

The ratio of test cases with N > 100 is less than 5%.

Output
For each test queries, print the answer.

Sample Input
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

Sample Output
21
41
36
36
32
43

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

1
数据结构上的一个线性表的冲突的解决,是不是用哈希算法怎么采用C语言的实现方式
0
子树的查询的一个算法的问题,如何利用C语言的方式去计算
0
马赛克拼接的一个算法的问题,采用C语言的技术如何实现的呢
0
寻找非递减的子序列的一个算法问题,采用C语言的技术实现的方式是?
0
连续的数字的一个判断的算法问题,问题采用C语言最佳的做法是怎么实现的
0
丢石头的游戏的一个算法的问题如何采用C语言的程序的编程的方法来实现的呢
0
典型网络的连通的问题的算法问题,如何采用C语言的程序的设计的方式来实现的
0
循环跳跃数的一个输出问题的算法,怎么采用C语言的程序的方式来实现
0
反推递增数列的一个算法的思路问题,怎么采用C语言的程序的设计的思想实现?
0
计数器实现的一个问题的算法,怎么才能采用C语言的程序的编写的过程的形式实现?
0
道路节点的最小花费的一个算法问题,怎么采用C语言的程序的代码实现的?
0
数组的平均切分的一个算法,怎么采用C语言的程序的编写的过程的方式怎么实现?
0
几何图形的碰撞的一个判断的算法,怎么采用C语言的程序的代码的编写的思路去实现的呢?
0
运用数据结构去实现纸牌的移动的一个算法,怎么采用C语言的程序的代码的编写的技术实现的?
0
锁的开闭的判断的问题的算法,怎么采用C语言程序代码的编写的技术实现的?
0
数据结构算法上面计算生日日期的一个算法问题,采用C语言的代码编写实现的思路是什么的?
0
简化了的星图的一个算法问题,怎么采用C语言程序编写的思路的代码实现的?
0
多次的计算的子序列算法问题,怎么采用的C语言程序编写的办法实现的?
0
重力测量的一个算法实现的问题,怎么采用 C语言编写代码的过程正确实现的?
0
求出最佳序列的一个问题算法,怎么采用C语言程序代码编写机制去实现的呢?