Peanut-Tang

IOI2020 集训队作业题单

这是个天坑，咕咕咕（2020.8.12~）。

文风借鉴 抄袭 Dreamunk 的 FJWC2020 题解合集。

这么快就 2020 了，回想我第一次参加省夏是初一的事（虽然那时参加的是普及组的）。

今年参加了 FJOI，直接就爆零了，唉。。。

今年参加中考了，全机房就我 whk 最差了 T_T。

今年我就要成为高中生了，在创新班会被踩的呀。

省夏因为参加国冬没去上课，现在一时兴起，想写写省夏的题解。

学习兔巨神和 Yuc 巨神，红的是主要看题解的，绿的是主要自己想的。（安慰自己，我这么菜，看题解是正常的，是正常的……）

本来题目想写「游记」的，但是因为我的博客一直咕着，过了都快一年，所以就改名为「回忆录」了。

下接 CSP-S && NOIP2020 爆炸记。

本人没有打这场 CF，但是场外看到这套题觉得很多题都很有趣，于是写个题解分享一下。

本场比赛链接：https://codeforces.com/contest/1395 。

前不久的初二初三互测，由于大佬们都不屑于出题，所以初三就派我出题了。

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

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

前言

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

非加强版链接

题意：

给定一棵有 $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$ 的点权。