Peanut-Tang

出给学弟的普及模拟赛，现在题解搬到这里来，估计也没人看了，坟贴一个。

出给学弟的普及模拟赛，现在题解搬到这里来，估计也没人看了，坟贴一个。

前言

这题算是我斯特林数的入门题，顺便安利大佬的博客，我是从这篇博客中学的斯特林数。

非加强版链接

题意：

给定一棵有 $3n+1$ 个结点的有根树，其中有 $n$ 个实点和 $2n+1$ 个虚点，每个实点有 $3$ 个儿子而所有虚点都没有儿子。实点从 $1$ 到 $n$ 编号，虚点从 $n+1$ 到 $3n+1$ 编号，且 $1$ 号点为根。

每个点都有一个点权，其中，虚点的点权由输入确定且只可能为 $0$ 或 $1$，而实点的点权为三个子结点的点权的众数。你需要支持三种操作（操作总数为 $m$）：

• 操作 $1$：输入 $1\ z$，表示将虛点 $z$ 的新点权设为其原点权异或 $1$ 后的值。
• 操作 $2$：输入 $2\ x\ y$，表示给定两实点 $x,y$，若 $x,y$ 不同且不为祖孙关系则将 $x$ 的父结点与 $y$ 的父结点交换。
• 操作 $3$：输入 $3\ x$，表示查询实点 $x$ 的点权。