Minimizing Pipe Clogs in a Gangster-Affected Sewage Tree

Central City’s sewage system is organized as a rooted tree: the central reservoir is the root and the houses are the leaves. Water flows along the edges (pipes) from the reservoir to every house. Recently, gangsters have occupied some houses, and as the mayor you want to stop water reaching them by clogging some pipes. If a pipe is clogged, then all houses in the subtree (i.e. all houses whose path from the reservoir includes that pipe) lose water.

Your goal is two‐fold:

1. Block water to every gangster-occupied house using the minimum number of clogged pipes.
2. Among all ways to use this minimum number of clogs, choose one that minimizes the number of innocent houses (those without gangsters) that lose water.

Because gangsters may appear or disappear over time at various houses, you will be given several queries. For each query, after updating the gangster status for a house, you must output two numbers:

• The minimum number of clogged pipes required.
• The minimum number of non‐gangster houses that lose water when using that many clogs.

Note: Houses correspond to the leaves of the tree. The tree is given as n nodes numbered 1 through n with node 1 being the reservoir. Each of the next n-1 lines describes a pipe from a parent node to a child node. Initially, a set of leaves has gangsters. Then, each query changes the status of a leaf: setting it to gangster (1) or clearing it (0).

The optimization can be formulated as follows. Suppose you select a set S of edges to clog. For every gangster leaf \(\ell\), at least one edge on the unique path from the root to \(\ell\) must be in S. Let the collateral damage be the number of non‐gangster leaves that end up disconnected from the reservoir (i.e. whose path contains an edge from S). You must choose S so that the pair
\( (\text{# clogged pipes},\; \text{collateral damage}) \)
is lexicographically minimal.

The formulas used are in \(\LaTeX\) as shown above.

inputFormat

The input begins with two integers n and Q where n is the number of nodes in the tree and Q is the number of queries.

Each of the next n-1 lines contains two integers u and v indicating a directed pipe from node u (the parent) to node v (the child). Node 1 is the root.

The next line contains an integer m, the number of leaves which initially have gangsters. The following line has m distinct integers indicating the indices (which are leaves) that initially have gangsters.

Then follow Q lines, each containing two integers v and s. Here, v is a leaf node and s is either 1 (gangster appears at node v) or 0 (gangster disappears from node v).

outputFormat

After each query, output two integers separated by a space: the minimum number of clogged pipes needed, and the minimum number of non‐gangster houses (leaves) that lose water in such an optimal configuration.

sample

5 3
1 2
1 3
2 4
2 5
1
4
5 1
4 0
5 0

1 0
1 0
0 0

</p>