自动搬运

查看原文

来自洛谷，原作者为

	XuYueming 没拿省一不改签

搬运于2025-08-24 22:52:33，当前版本为作者最后更新于2025-06-21 18:55:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

题目链接：洛谷。

庚昊的体验。

题意简述

维护一张无向图图，初始两个点，通过一条边相连。$q$ 次操作：

• W x：新建点，和 $x$ 连边。
• Z x：新建点，和 $x$ 所有直接相连的点连边。
• ? x：查询有几个点和 $x$ 相连。

题目分析

妙妙题。

发现 Z 操作很像把 $x$ 复制一遍，相当于一个新的版本。提示我们对操作建树，$u$ 继承了 $\operatorname{fa}(u)$ 所有对应的连边状态。

那么 W 操作就是先把 $x$ 复制一遍，在新版 $x$ 上与新建点「连边」（这里连边是原图上相连的意思，并非树边，称之为「W 边」），这样不会让之前的点错误继承这次操作。

原图上，两个点 $u,v$ 相连，当且仅当操作树上 $u$ 的某一个祖先 $u'$ 和 $v$ 的某一个祖先 $v'$，通过 W 边相连。

那么问题变为了求 $x$ 的每一个祖先，所有连出 W 边指向的点，在操作树上的子树中有几个点，这里需要对点做区分，不能算上 W 操作复制的版本。

稍微分类讨论一下。对于树根，相当于单点加子树和；对于非树根，修改的时候将树根 W 边父亲单点修改，链查询。

均可以树状数组做到 $\mathcal{O}(n\log n)$。

可以 LCT 做到在线，相信大家都会。

代码

离线树状数组、在线 LCT 的代码，见我博客。