P4332 [SHOI2014] Trinary Neural Tree

Computational neuroscience, as an emerging interdisciplinary field, has been a research hotspot in recent years. A kind of neural tissue called SHOI has attracted great attention because of its close relationship with a recently discovered compound, SHTSC. A SHOI tissue consists of several SHOI cells forming a strict tree structure. Each SHOI cell has exactly one output terminal, called an axon. Except for a special SHOI cell called the root cell whose output serves as the output of the entire tissue, the axons of all other cells connect to their parent SHOI cell. Each cell also has exactly three input terminals, called dendrites, which receive information from its child cells or from other neural tissues. The signaling mechanism of SHOI cells is simple, with only $0$ and $1$. Each SHOI cell outputs the majority value among the three input signals, i.e., whichever of $0$ or $1$ appears more times among its three inputs. You are given the structure of a SHOI tissue and the changes of external neural inputs. Please simulate the output of the SHOI tissue.

- The first line contains an integer $n$, the total number of SHOI cells. Cells are numbered $1 \sim n$, and cell $1$ is the root cell. - The next $n$ lines each contain three integers $x_1, x_2, x_3$, describing the dendrite connections of cells $1 \sim n$, respectively. If $1 < x_i \leq n$, it connects to the axon of cell $x_i$. If $n < x_i \leq 3n+1$, it connects to the external input with index $x_i$. The input guarantees that the given SHOI tissue is valid, and for each cell the three $x_i$ are pairwise distinct. - The next line contains $2n+1$ integers (each $0$ or $1$), giving the initial values of the external inputs in the order of indices $n+1, n+2, \dots, 3n+1$. - The next line contains an integer $q$, the number of operations. - The next $q$ lines each contain one integer $x$, indicating that the external input with index $x$ (where $n < x \leq 3n+1$) toggles its value.

Output $q$ lines. For the $i$-th change of an external input, print one integer: the output of the root cell after this change.

- For $10 \%$ of the testdata, $1 \leq n \leq 10^3$, $1 \leq q \leq 10^3$. - For $30 \%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq q \leq 10^5$. - For $100 \%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $1 \leq q \leq 5 \times 10^5$. Translated by ChatGPT 5