zyf 的题解，写得比我好 QAQ

不难发现，答案为 YES，当且仅当所有点的出度均为 1。

考虑如何维护每个点的出度。

暴力的做法是对于每个点维护两个 set，分别表示当前与之相连/不相连的点，暴力删点加点。如果没有 $t=4$，不难发现总操作次数是 $\mathcal O(n+q)$ 级别的，可以获得 60 pts。

（据说这道题可以通过玄学暴力优化在民间数据拿到满分，毕竟这题的数据并不好造，很难有极限数据）

（然而我考场上尝试玄学暴力乱搞，结果全输出 NO，爆零了 QAQ）

upd：现在还没有出数据，但据说全输出 NO 能有 45 pts？乱搞选手赢麻了。

再次 upd：出数据了，我这种乱搞法居然 50pts，赢麻了，但是 rp-- 了 QAQ。

计算了一下，前 60 pts 暴力，后面全输出 NO，能有 80 pts，已经不比正解低多少了。

这道题的核心就是维护出度为 1 的点数，而有了 $t=4$ 的操作会变得非常棘手，没有任何数据结构可以维护。

一般来说（至少以窝之前打的一场 CF 看来），这种情况可以转向随机化。

考虑哈希。对每个点赋一个独一无二的权值（我采用了类似字符串哈希的构造方式），设第 $i$ 个点点权为 $a_i$，定义 $tot=\sum\limits_{i=1}^n a_i,ans=\sum\limits_{i=1}^n deg_i\times a_i$。

其中 $deg_i$ 表示点 $i$ 的出度。

由于点权都是独一无二的，若 $ans=tot$，那么就有极大的概率满足 $\forall i\in [1,n],deg_i=1$。

$tot$ 可以直接计算，而 $ans$ 的维护也相当简单，单次操作时间复杂度 $\mathcal O(1)$。

总时间复杂度为 $\mathcal O(n)$，目前在 InfOJ 上的民间数据这种方法可以拿到满分。

如果还不保险，还可以多取几个模数或点权。

upd：似乎不用我这样写，把求和改成异或，直接随机权值就完全能过了 /kel

std 似乎是直接插排，但我并不会这种做法，讲一下我的想法。

首先，想一想就可以发现，$a_i$ 插排后的位置即为原序列中 $\lt a_i$ 的数的数量加上前 $i$ 个数中等于 $a_i$ 的数量。

发现这题的修改数量和 $n$ 的范围都非常小，不难想到标算是 $\mathcal{O}(n^2)$ 级的。

那么可以设计出以下算法：

首先设 $cnt_x$ 为 $a_x$ 插排后在原序列中的位置。

根据上述算法 $\mathcal{O}(n^2)$ 算出 $cnt$ 数组，然后进入询问。

对于修改操作，直接暴力地除去原 $a_x$ 的贡献，计算 $v$ 的贡献，并把 $cnt_x$ 再求出来。

对于询问操作，直接输出 $cnt$ 即可。

时间复杂度 $\mathcal{O}(n^2 + 5 \times 10^3 \times n)$，常数有点大，洛谷和 CCF 的评测机应该是能卡过去，但 COGS 需要一点常数优化，而且要手动吸氧（开O2）

定义 $f(u,k)$ 表示以 $u$ 为根的子树里有 $k$ 个节点与 $u$ 联通的最小道路，$size(u)$ 为 $u$ 的子树内节点个数。

初始状态：$\forall u \in [1,n],f(u,1)=|son_u|$，其中 $|son_u|$ 表示 $u$ 的出边个数。

转移方程：

$$\sum\limits_{v\in son_u,j\in [1,size(u)],k\in [1,size(v)]} f(u,j+k)=\min\{f(u,j)+f(v,k)-2\}$$

其中 $-2$ 是因为最初 $u,v$ 两点的连边被断开，多加的 $2$ 要在这里减回来。

感性理解一下为什么说时间复杂度是 $\Theta(n^2)$ 的：

发现主要的时间复杂度是在 $j,k$ 的枚举上，而 $j,k$ 的枚举其实等价于枚举点对。

原因不难理解，每两个节点只有在它们的 LCA 处会被枚举到。

因此，总的时间复杂度是 $\Theta(n^2)$

（测试题解）

(注：此文设题中输入的图为 $G_1$，对应的完全图为 $G_2$，对应的补图为 $G_3$)

首先不难想到暴力思路：直接将 $G_2$ 建出来，跑一遍 MST 即可。

然而这样时间显然无法承受。

但是这道题显然有别的思路，考虑从特殊的边长：$0$ 和 $1$ 入手。

题中所给的边长为 $1$ 的边视为断边，建出 $G_3$，不难发现，答案就是补图的连通块数量减 $1$。

我们只需要算出连通块的数量即可，可以用并查集处理。

然而边数仍然很多，直接暴力求连通块很容易 TLE/MLE。

这时这个题目巧妙的地方就来了：我们可以将求解拆成两块，再合并答案。

首先发现，在原图 $G_1$ 中，设点 $i$ 的度数为 $deg_i$，不难发现$\sum\limits_{i=1}^n deg_i =2m$

那么根据抽屉原理，其中度数最小的点度数不超过 $\frac{2m}{n}$ ，设该点为 $u$ .

则可以先将 $G_1$ 中与 $u$ 没有连边的点和 $u$ 暴力合并，和 $u$ 有连边的点存储下来，暴力合并。

其中暴力合并的复杂度为 $O(N)$，则整体的时间复杂度为 $O(N+N\times \frac{2m}{N})=O(N+M)$.