标签：连通 子树 考后 省选 siz cnt Alice 节点 NOI

文化课补完了，但是考试考炸了，所以来补题。

D1T1 火车站 station

实际上只需要判断从 \(x\) 能否一直向一个方向移动且每个位置能不能作为这个方向的终点站。

区间覆盖差分一下即可。

提交记录：Submission - QOJ

D1T2 城市建造 cities

一个连通块中只能有一个点被选中。

由于连通块大小是 \(\left\lfloor n/cnt\right\rfloor\) 和 \(\left\lceil n/cnt\right\rceil\)，只有 \(O(\sqrt{n})\) 中，可以枚举连通块大小。

考虑树上怎么做，假设当前枚举的连通块大小 \(siz\)，可能的连通块个数 \(cnt\)，那么有 \(cnt\) 个节点被选中，且断边后断成了 \(cnt\) 个连通块，也就是 \(cnt\) 个节点有 \(cnt-1\) 条边，因此合法方案实际上是一棵树（这个性质在考场上认为是菊花或是链之类的，没拿到部分分）。

考虑一个树形 DP，设 \(f_v\) 为 \(v\) 与父亲的连边被断开，即 \(v\) 子树内部划分成大小为 \(siz\) 或 \(siz+1\) 的连通块的方案数。

一棵树的性质同样揭示了另一个事实：如果 \(v\) 与父亲的连边不断开，那么 \(v\) 一定是整体并入其父亲所在连通块的，也就只和子树大小 \(siz_v\) 有关了。

这样对于 \(u\) 的儿子 \(v\)，不同的 \(siz_v\) 直接对应不同的处理方式：

• \(siz_v>siz\)，不可能与 \(u\) 在同一连通块，\((u,v)\) 必须断开。

• \(siz_v=siz\)，既可能与 \(u\) 在同一连通块，也可能单独成连通块。

• \(siz_v<siz\)，一定与 \(u\) 在同一连通块。

这样我们只需要统计第一种情况是否内部划分都合法，第三种情况之和与 \(u\) 拼在一起是否合法，同时将的第一种情况的方案数累成即为答案。还有一同时情况为：不存在小于 \(siz\) 的，此时若 \(siz=1\) 或存在等于 \(siz\) 的子树 \(v\) 才合法，且方案数乘上满足条件的 \(v\) 的个数（如果 \(u\) 单独成块也合法也要计入）。

这样在每个节点统计答案，默认其父亲及其他子树都不断开。

---

放到图上，由于删去选中节点的全部连边后不连通，容易想到点双连通分量，这样一个点双内如果选取超过一个且有没有选取的，无法达到不连通的条件。因此一个点双要么全不选，要么全选，要么选一个。反映到圆方树上就是选取点击构成的树，叶子节点一定全是圆点。

根据这个性质同样可以讨论圆点方点后 DP，\(f_u\) 定义相同。

对于圆点，和上面树的情况讨论是一致的；对于方点，如果断开了其与父亲的连边，那么意味着其与儿子连边要么不断开要么全部断开，因此在对方点 DP 时，只需要考虑全部断开是否合法即可。

要注意的是，图上和树上不同之处在于即便 \(siz_v=siz\)，断开 \((u,v)\) 后不一点合法，因为这代表着 \(v\) 对应所有圆点连边都将断开，而不是像树上作为一个整体。

这样大致就是全部算法流程，还存在的问题是枚举到 \(\left\lfloor n/cnt\right\rfloor\) 时有可能存在方案至划分成了大小为 \(\left\lceil n/cnt\right\rceil\) 的连通块，这样会算重。可以容斥，减去 \(\left\lceil n/cnt\right\rceil\) 对应 \(k=0\) 的情况。

---

由于复杂度一定拉满，需要大面积卡常：

• 只在重心位置统计答案，重心一定会被选中，否则被选中的部分是其一个子树，大小不超过一半，也就和其余部分大小相差 \(1\) 以上。

• DFS 时按照 DFS 序重标号，\(O(\sqrt{n})\) 次 DFS 使用非递归 DFS。

• 使用邻接表而不是 vector。

• 如果存在大小大于 \(siz\) 的子树内部不合法或是大小小于 \(siz\) 的子树大小之和超过了 \(siz\)，一定没有合法方案，可以不再枚举子树。

• 如果 \(siz_u<siz\)，一定没有合法方案，这一处能带来极大的优化。

提交记录（不卡常，易读）：Submission - QOJ

提交记录（卡常，不易读）：Submission - QOJ

D1T3 人员调度 transfer

先考虑静态的情况。

可以看做一个二分图，左部点是职员，右部点是部门，职员到部分连带权边，要求一个最大权匹配（注意只要求权值最大）。

这样可以看做是费用流模型，每次增广最长路，直到增广路权值为负。起初增广的一定是权值较大的，后面退流时因为保证增广路权值非负，所以不会把先增广的退流。换言之，贪心地加入权值更大的直到不能加一定是正确的。

这样就摆脱了权值的限制，变成一个二分图匹配，选择一些职员，判断他们可以完全匹配就利用 Hall 定理，放在本题就是每个节点子树选择的职员总数不超过子树大小。

需要支持无序加入职员，我们需要维护数据结构，支持判断子树是否填满，以及查询最小值。

两棵线段树，一棵维护子树是否填满，维护信息 \(siz_u-cnt_u\) 表示剩余空位置，这样在 \(u\) 节点加入一个元素时判断是否填满只需要查询 \((1,u)\) 路径上的值是否都为正，如果都为正可以直接加入，否则在深度最大的被填满的节点对应子树内找到最小权值，如果当前加入的权值更大，则删除最小权值对应元素加入当前元素。子树最小权值用另一棵线段树维护，在叶子节点挂 multiset。找到深度最大的被填满的节点等价于找根链上 \(siz_u-cnt_u\) 最小且 DFS 序最大的一个。

带修改可以套一个线段树分治，总复杂度 \(\Theta((n+m)\log^2 n\log m)\)

提交记录：Submission - QOJ

D2T1 过河卒 zu

不是博弈论，是博弈论暴搜。

图很小，可以压成 \(10^6\) 的状态记录三个棋子的位置，合法转移直接连边。

不好解决的问题是可能出现平局——成环，这样不能从起始状态开始搜。改成从每个结束状态开始搜，由于根据步数的奇偶性可以判断出当前是谁的回合，我们只需要拓扑转移即可。

如果一个状态当前被转移到的都是必败状态，那么一直取步数的 \(\max\)，一旦出现必胜决策可以直接入队，由于 BFS，此时步数一定最小，且在当前位置决策者一定会选这种必胜决策。也就是魔改了一下拓扑排序。

在答案处要注意的是，如果是必败状态且初始状态处于一个环中，那么会选择走环来达到不败的情况，要特判一下。（在转移过程中由于没有被完全剥出的节点不会入队，实际上也是存在不败一定选不败）

提交记录：Submission - QOJ

没有想到的是如何处理平局以及压成状态建图搜索的简单转换。

---

差不多的题：AtCoder-ABC261Ex Game on Graph

不用压状态了，但是要区分走到这个节点是谁的回合，可以把点拆开，建反图之类的的操作和上面类似。

有边权，所以后手一定是类似拓扑排序地所有点的值取 \(\max\) 才入队，否则会选择平局；先手则是取 \(\min\)，但是不能保证第一次更新就是 \(\min\)，而多次更新的复杂度不能保证，把队列改成堆就可以了。

D2T2 填数游戏 game

完全想反了呀！！！树的情况完全不会做呀！！！

似乎是逐步分析特殊性质得到正解的典型题，几乎是复述了 ZCPB 的题解。

对于 Alice 的方案，Bob 会选择相同数最小的一个，Alice 会最大化相同数的最小值，或是最小化不同数的最大值。

性质 A

只需要判断是否合法。

二元关系考虑连边，对于每个连通块，如果 \(|E|>|V|\) 则不合法。

（我为啥考场上写的二分图匹配？）

性质 B

\(|E|=|V|\)，是环。

如果 \(S_i\cap T_i=\varnothing\)，那么没有贡献，如果 \(|S_i\cap T_i|=1\)，那么一定选有交的一个，如果 \(|S_i\cap T_i|=2\)，两个都可以选。

在环上一定要么都选左侧要么都选右侧，考虑设 \(cnt1,cnt2,cnt3\) 分别表示只能选左侧、只能选右侧和两侧都可以选的个数，那么实际上 Alice 会把 \(cnt3\) 分给 \(cnt1,cnt2\) 使得二者最小值最大，如果 \(cnt1+cnt3<cnt2\) 或是 \(cnt2+cnt3<cnt1\)，则答案是 \(cnt1+cnt3\) 或 \(cnt2+cnt3\)，反之策略是平均分配，即 \(\left\lfloor\dfrac{cnt1+cnt2+cnt3}{2}\right\rfloor\)。

基环树

树部分的边只能选儿子一侧的，统计一下加上环部分答案即可。

性质 C

这个性质没啥用！

性质 D

如果是基环树同上，下面讨论如果是树，这个特殊性质是所有边都可以选双向。

树性质是找到一个节点作为根，所有边都选儿子一侧的。

考虑一条边 \((u,v)\) 钦定选择 \(u\) 之后，\(u\) 一侧子树的所有节点如果为根，那么 \((u,v)\) 这条边应当选择 \(v\)，所以选择 \(u\) 会使 \(u\) 一侧子树的不同数增加 \(1\)，同理使 \(v\) 一侧的相同数增加 \(1\)。

定义一条边的方向为选择的一端，考虑两条相向的边，它们对相同数贡献的点集无交，如果都调转方向变成相背的边，贡献的点集是全集，而 Alice 的目的是最大化相同数最小值，所以 Alice 的构造方案一定不存在相向的边，进一步地说，Alice 的构造方案一定是选一个节点作为根，所有边都选叶子一侧的。

（其实得到这个性质就可以换根做了。）

实际上，有多少边直接或间接指向某个节点，那么这个节点就被贡献了多少次不同数，因此 Bob 会选择被指向最多的一个节点，结合上面对 Alice 方案的分析，就是 Alice 构造树深度最深的节点。

因此 Alice 目的使树高尽量小，所以会选择树的直径中点作为根，答案就是所有边数减去树高，即 \(n-1-\left\lceil\dfrac{d}{2}\right\rceil\)，\(d\) 是直径。

树

容易想到的是把两个端点都能选的边权值设为 \(1\)，其余设为 \(0\)，跑一个带权直径处理。

但是还有一些只能选一端的边是钦定了的，这些也要考虑在内。其实就是性质 C 的做法，给指向子树内增加 \(1\)，差分做一下就行。

然后大致也是找到一个节点为根，所有两端都能选的边选择儿子一侧，Bob 会选择点权（也就是被贡献不同数）加到根路径上边权之和最大的一个，Alice 目的是最小化这个最大值。所以要求一个有端点点权的带权直径。会产生答案的总边数（有交的）减去直径除以二向下取整即为答案。

这个看着好像很怪，似乎会有找不到直径中点的情况，实际上仔细思考发现找不到直径中点说明一段点权很大，那么向这一端移动过程中会经过点权与这一端很接近的位置，这才是直径。也就是这种带权直径端点不一定是叶子。

提交记录：Submission - QOJ

标签：连通,子树,考后,省选,siz,cnt,Alice,节点,NOI
From： https://www.cnblogs.com/SoyTony/p/Problems_in_NOI_Unified_Provincial_Team_Selection_2023.h