网络修复
[Description]
经过同学们的改造,信奥班的网络成为了一棵有 N 个节点的无根树,每一个节点代表一台计
算机(编号 1 ~ N),每一条边代表一条网络线路(编号 1 ~ (N - 1))。
有一天,Gemini 偶然发现了 Kroulis 以前写过一个杀毒软件;于是他毫不犹豫地找到了病毒
库,运行了里面所有的病毒。(我:什么心态?Gemini:出题需要嘛!我:不对怎么精分现场
了?Gemini:怪我咯?!)
于是这一下,每一条网络线路都断开了。在收拾了 Gemini 后,同学们开始抢修网络。
抢修过程持续了 T 个时刻,在每一时刻有可能发生下面两件事之一:
1. 某一条网络线路恢复通畅;
2. Gemini 想知道某两台计算机之间是否已经连通,如果连通,从一台计算机到另一台计
算机要经过多少条网络线路。
[Input]
第一行两个整数 N,T。
以下 N - 1 行每行两个整数 Ai,Bi,表示第 i 条网络线路直接连接计算机 Ai 和 Bi。
以下 T 行顺序给出 T 个事件,每行形如“C e”或“Q a b”(其中 e,a,b 是整数)。“C e”
代表这一时刻第 e 条网络线路恢复通畅;“Q a b”代表查询第 a 台计算机和第 b 台计算机之
间是否连通。
[Output]
为了避免大量输出,你需要按照如下方式处理你的输出。
声明一个 32 位有符号整型变量 R,赋值为 0。将所有事件按照发生顺序(即输入文件中给出
的顺序)编号为 1 ~ T。按以下指示遍历所有操作。
如果第 i 个事件为“C e”,则不对 R 做任何处理。
如果第 i 个事件为“Q a b”,且 a,b 不连通,则 R = R ^ (i + a + b)。
如果第 i 个事件为“Q a b”,且 a,b 连通,且从计算机 a 到计算机 b 要经过 K 条网络线路,
则 R = (R + (i ^ K)) % 998244353。
最终输出 R 的值。
(^代表二进制下的异或操作,%代表取模操作。)