A Tree With More Root Nodes Is a Better Tree

Time limit2sMemory limit1024 MB

Summary

Maintain a mixed directed/undirected tree under edge-direction updates and after each update report how many nodes can reach all others.

Level: Hard8 of 10
Topics: Tree, DFS, Implementation, Graph
Solved: No attempts yet

Problem

There is a graph with $N$ nodes and $N-1$ edges. The nodes are numbered from $1$ to $N$ , and each edge may be directed or undirected. If the direction is removed from every edge, this graph becomes a tree.

A node is called a 'root node' if a path exists from it to every other node. The 'goodness' of this graph is defined as the number of root nodes. Perform the following queries.

Change the edge connecting $u$ and $v$ into the directed edge $u \rightarrow v$ .
Change the edge connecting $u$ and $v$ into the directed edge $u \leftarrow v$ .
Change the edge connecting $u$ and $v$ into an undirected edge.

The results of the queries accumulate in the graph.

Input

The first line gives the number of nodes $N$ .

From the second line, $N-1$ lines give information about the edges. Each edge is given as three space-separated tokens $U_i$ , $D_i$ , $V_i$ , where $U_i$ and $V_i$ are integers denoting node numbers and $D_i$ is a string denoting direction, one of ->, <-, --.

If $D_i$ is ->, the $i$ -th edge is the directed edge $U_i \rightarrow V_i$ .
If $D_i$ is <-, the $i$ -th edge is the directed edge $U_i \leftarrow V_i$ .
If $D_i$ is --, the $i$ -th edge is the undirected edge $U_i \leftrightarrow V_i$ .

The next line gives the number of queries to perform, $Q$ .

From the next line, $Q$ lines give the queries in order. The $i$ -th line gives three tokens $u_i$ $d_i$ $v_i$ , where $u_i$ and $v_i$ are integers denoting node numbers and $d_i$ is a string denoting direction, one of ->, <-, --.

If $d_i$ is ->, set the $i$ -th edge to the directed edge $u_i \rightarrow v_i$ .
If $d_i$ is <-, set the $i$ -th edge to the directed edge $u_i \leftarrow v_i$ .
If $d_i$ is --, set the $i$ -th edge to the undirected edge $u_i \leftrightarrow v_i$ .

Output

After each query, print the 'goodness' of the graph on its own line.

Constraints

$2 \le N \le 10^5$
$1 \le Q \le 10^5$
$1 \le U_i, V_i \le N$ ( $1 \le i \le N-1$ )
$U_i \ne V_i$ ( $1 \le i \le N-1$ )
The graph formed by connecting every $U_i$ and $V_i$ with an undirected edge is a tree.
The given graph contains an edge connecting $u_i$ and $v_i$ .

Examples1

Example 1

Input

5
1 -- 2
2 -> 3
2 <- 4
3 -- 5
5
2 -- 4
2 -> 4
5 -> 3
2 -- 3
3 -- 5

Expected output