INS14M - Terrorist Attack

no tags 

In his final interview Digo is given a map of a city containing N junctions connected by roads of length 1. There is only one path between any two junctions. Each junction has a unique index between 1 and N (inclusive). There are M civilians in the city. Everyday, each civilian visits a set of junctions.

There are military camps built at certain junctions. The terrorists are planning to attack the city by targeting some junctions. However due to the presence of military camps, there is a limit to the size of explosion they can make at any particular junction. The intensity of the bomb planted at a junction is equal to the minimum distance from any military camp to the targeted junction. The damage of all civilians passing through a targeted junction increases by the intensity of the bomb dropped at the junction. The military camps set up and the terrorist targets are given in the form of the following queries:

1 J : Meaning that a new military camp is set up at junction J
2 J : Meaning that the junction J is targeted by terrorists
3 J : Print the total damage done till now to all civilians visiting junction J

Initially there is exactly one military camp at junction 1. The initial damage of all civilians is given to you.

Input

First line contains 3 integers N, M, Q. N is the number of junctions, M is the number of civilians and Q is the number of queries to follow.

Next N-1 lines contains 2 integers U and V (denoting that there is a road connecting U and V).

Next M lines contains one integer each. The ith line contains integer a[i] representing the initial damage of the ith civilian. Next M lines contain the description of the junctions visited by the ith civilian (First integer of every line is X, the number of junctions visited by the ith civilian, followed by X integers representing the respective junctions).

Next Q lines give the corresponding queries. Each query can be described by two integers T, J, where T is the type of query (which can be 1 or 2 or 3) and J is the respective junction of the query.

Output

For all the queries of type 3 print an integer answering the query.

Constraints

1 <= N <= 50000
1 <= M <= 10000
1 <= Q <= 50000
1 <= X, V, U, J <= N
1 <= a[i] <= 1000

Sum of all the junctions crossed by all the civilians is less than 50001

Note: The Final answer will fit in 64 bit signed integer.

Example

Sample Input:
3 1 3
1 2
2 3
5
2 2 3
3 3
2 3
3 3

Sample Output:
5
7

hide comments
[Rampage] Blue.Mary: 2022-09-05 11:16:26

Problem description is clear, whereas sample ouput is not helpful for understanding the problem. However this problem is solveable only by the problem description.

smso: 2022-09-05 06:47:56

No explanation is given for the output of the only test case. Besides, type 2 query is not included. Problem is not recommended.

Min_25: 2014-04-13 20:47:15

@Surya kiran
Thank you for replying. I try to find a better solution.

Surya kiran: 2014-04-13 19:37:10

@Min_25 : In pyramid you can do nearly 5*10^6 operations per second, your complexity is not intended. Try to find a better way.

Min_25: 2014-03-29 07:46:30

My code's time complexity is O(Q * K^0.5) (K is about 50,000 in this problem).

If this time complexity is intended, I think this time limit is very strict
because it will take about 1 second (on the Pyramid) to solve the worst testcase.

Last edit: 2014-03-29 08:49:11

Added by:Surya Kiran
Date:2014-03-20
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Insomnia 2014