CF1010D Mars rover

Natasha 驾驶着火星车在火星上旅行。但突然，火星车坏了，具体来说——是内部的逻辑电路出了问题。该电路是一个无向树（连通无环图），以顶点 $1$ 为根，其中每个叶子节点（不包括根）是一个输入，其余所有顶点都是逻辑元件，包括根节点，根节点作为输出。每个输入端会输入一个比特，输出端会输出一个比特。 逻辑元件共有四种类型：[AND](https://en.wikipedia.org/wiki/Logical_conjunction)（$2$ 个输入）、[OR](https://en.wikipedia.org/wiki/Logical_disjunction)（$2$ 个输入）、[XOR](https://en.wikipedia.org/wiki/Exclusive_or)（$2$ 个输入）、[NOT](https://en.wikipedia.org/wiki/Negation)（$1$ 个输入）。逻辑元件从其直接子节点（输入）获取值，并返回其对应逻辑函数的结果。Natasha 已经知道了火星车的逻辑电路结构，并且知道只有一个输入端出现了故障。为了修好火星车，她需要改变这个输入端的值。 对于每个输入端，判断如果 Natasha 改变该输入端的值，最终输出会是多少。

第一行包含一个整数 $n$（$2 \le n \le 10^6$），表示图中顶点的数量（包括输入端和逻辑元件）。 接下来的 $n$ 行中，第 $i$ 行描述第 $i$ 个顶点：第一项为 "AND"、"OR"、"XOR"、"NOT" 或 "IN"（表示该顶点为输入端），如果该顶点为 "IN"，则接下来是该输入端的值（$0$ 或 $1$）；否则，接下来是该逻辑元件的输入顶点编号："AND"、"OR"、"XOR" 有 $2$ 个输入，"NOT" 有 $1$ 个输入。顶点编号从 $1$ 开始。 保证输入数据描述的是一个合法的逻辑电路，且输出由顶点 $1$ 产生。

输出一个仅包含字符 '0' 和 '1' 的字符串——对于每个输入端，按照其顶点编号递增的顺序，输出 Natasha 改变该输入端值后，最终输出端的值。

示例中的原始电路（在未改变输入时）如下图所示：  绿色表示比特 '1'，黄色表示比特 '0'。 如果 Natasha 将输入比特 $2$ 改为 $0$，则输出为 $1$。 如果 Natasha 将输入比特 $3$ 改为 $0$，则输出为 $0$。 如果 Natasha 将输入比特 $6$ 改为 $1$，则输出为 $1$。 如果 Natasha 将输入比特 $8$ 改为 $0$，则输出为 $1$。 如果 Natasha 将输入比特 $9$ 改为 $0$，则输出为 $0$。 由 ChatGPT 4.1 翻译