H. Pirogolandia

Execution time limit is 1 second

Runtime memory usage limit is 64 megabytes

In Pie Land, a country where residents have a deep love for pies, there are n bakeries, each uniquely numbered from 1 to n. Each bakery has a warehouse storing a specific number of pies, denoted as a[i] for the bakery numbered i.

The bakeries are connected by n - 1 roads, each uniquely numbered from 1 to n - 1. The i-th road connects bakeries u[i] and v[i], allowing pies to be transported between these bakeries in both directions.

A path between two bakeries u and v is a sequence of unique bakery numbers p[1], p[2], ..., p[k], where there is a road between each consecutive pair p[i] and p[i+1]. The path starts at p[1] = u and ends at p[k] = v. There is exactly one such path between any two bakeries that does not revisit any bakery.

Occasionally, earthquakes block some roads, preventing pie transportation. Conversely, road repairs can unblock these roads. Each road can either be blocked or unblocked.

The component of a bakery u is the set of all bakeries reachable from u without crossing any blocked roads, including u itself.

Kozak Vus, a renowned pie enthusiast in Pie Land, is known for consuming more pies than anyone else at the annual pie festival.

You need to handle m events related to bakeries, roads, and Kozak Vus, responding to specific queries. There are 7 types of queries:

Toggle the state of the road numbered p. If it was blocked, unblock it, and vice versa.
Add w pies to each bakery in the component of bakery p.
Transfer all pies from bakeries in the component of bakery p to bakery p itself, emptying the others.
Report the number of pies in the warehouse of bakery p.
Report the total number of pies in the component of bakery p.
Kozak Vus eats all pies from the component of bakery p, setting their pie counts to 0.
Determine the minimum number of roads that need repair for Kozak Vus to access all pies in Pie Land, starting from any bakery and using only unblocked roads.

Queries of types 4, 5, and 7 are informational and do not alter the state of bakeries or roads.

Interaction

Implement the following functions:

void init(integer n, array of integers u, array of integers v, array of integers b, array of integers a, integer g)

n: Number of bakeries.
u[i] and v[i]: Bakeries connected by the i-th road.
b[i]: 1 if the i-th road is blocked, 0 otherwise.
a[i]: Number of pies in the i-th bakery.
g: Block number.
This function initializes the state of Pie Land.

void query_1(integer p)

p: Road number to toggle its state.

void query_2(integer p, integer w)

p: Bakery number.
w: Pies to add to each bakery in the component of p.

void query_3(integer p)

p: Bakery number.

integer query_4(integer p)

p: Bakery number.
Returns the number of pies in bakery p.

integer query_5(integer p)

p: Bakery number.
Returns the total pies in the component of bakery p.

void query_6(integer p)

p: Bakery number.

integer query_7()

Returns the minimum number of roads to repair for Kozak Vus to access all pies.

Input Format

The first line contains three integers n, m, and g. The next n − 1 lines describe the roads with pairs u[i] and v[i]. A string of n − 1 symbols follows, indicating blocked (1) or unblocked (0) roads. The next line lists the pies in each bakery. The following m lines describe the queries.

Output Format

For each query of type 4, 5, and 7, output the result on a separate line.

Evaluation

(2 points) n ⩽ 3,000; m ⩽ 3,000; no type 1 and 7 queries; all roads initially blocked.
(3 points) n ⩽ 3,000; m ⩽ 3,000; no type 1 and 7 queries; all roads initially unblocked.
(5 points) n ⩽ 3,000; m ⩽ 3,000; no type 1 and 7 queries.
(6 points) n ⩽ 3,000; m ⩽ 3,000; no type 7 queries.
(8 points) n ⩽ 3,000; m ⩽ 3,000.
(10 points) no type 1 and 7 queries.
(16 points) no type 7 queries; type 1 queries only unblock roads.
(15 points) no type 1 queries.
(9 points) no type 7 queries.
(17 points) each bakery connects to at most two others.
(9 points) no additional restrictions.

Note

Illustrations depict bakeries as circles with two numbers: the bakery number and the number of pies. Solid lines represent unblocked roads, while dashed lines indicate blocked roads.