专栏文章

题解：CF1464F My Beautiful Madness

ccomplexor管理员
CF1464F题解参与者 4已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mipcfqen
此快照首次捕获于
2025/12/03 09:43
3 个月前
此快照最后确认于
2025/12/03 09:43
3 个月前
查看原文

题意简述

给定一棵 nn 个点的树。
对于点 u,vu,v，定义它们之间的距离 dis(u,v)dis(u,v) 为树上两点间简单路径的边数。
对于点 uu，路径 PP，定义它们之间的距离 dis(u,P)=min⁡v∈P{dis(u,v)}dis(u,P)=\displaystyle\min_{v\in P}\{dis(u,v)\}。
对于路径 P,QP,Q，定义它们之间的距离 dis(P,Q)=min⁡u∈P,v∈Q{dis(u,v)}dis(P,Q)=\displaystyle\min_{u\in P,v\in Q}\{dis(u,v)\}。
现在有一个初始为空的可重路径 SS，有 QQ 次操作，操作共有三种：
  1. 往 SS 中加入一条路径 PP。
  2. 从 SS 中删除一条路径 PP。
  3. 给定 dd，问是否存在点 xx，满足 ∀P∈S,dis(x,S)≤d\forall P\in S,dis(x,S)\leq d。
另一个版本是只有前两种操作，每次后求出 F=min⁡x{max⁡P∈S{dis(x,P)}F=\displaystyle\min_x\{\max_{P\in S}\{dis(x,P)\}。

前置结论

下面两个做法都要用到一个结论：
  • 对于点集 SS，设 u,v∈Su,v\in S 满足 dis(u,v)=max⁡x,y∈S{dis(x,y)}dis(u,v)=\displaystyle\max_{x,y\in S}\{dis(x,y)\}，也就是 u,vu,v 是点集 SS 中距离最远的一对点。那么对于树上任意的点 xx，它到点集 SS 的最远距离为 max⁡y∈S{dis(x,y)}=max⁡{dis(x,u),dis(x,v)}\displaystyle\max_{y\in S}\{dis(x,y)\}=\max\{dis(x,u),dis(x,v)\}。

解法一

求 FF 可以二分转化成 log⁡n\log n 次上面的操作 3。
对于路径问题，一个思路是将考虑一条路径变成考虑若干关键点。而一条路径只有一个 lcalca，所以考虑 lcalca 可能有用。
随便找一个树根，对于点 xx 记其 kk 级祖先为 anc(x,k)anc(x,k)，子树为 TxT_x。
考虑操作 3 中什么时候存在满足条件的 xx。对于每条路径 PP，一个必要条件是 xx 要在 anc(lca(P),d)anc(lca(P),d) 的子树中，否则一定有 dis(x,P)>ddis(x,P)>d。既然是子树限制，那么考虑最深的 lca(P)lca(P)，记 u=anc(lca(P),d)u=anc(lca(P),d)，那么 xx 一定在 TuT_u 中。而为了尽可能满足其他路径的限制，x=ux=u 看起来就很好。事实上，可以证明存在满足条件的 xx，当且仅当 uu 满足条件，证明如下：
  1. 显然 uu 满足条件的时候，已经找到满足条件的 xx。
  2. 如果 uu 不满足条件，那么存在 P∈SP\in S，使得 dis(u,S)>ddis(u,S)>d。
  3. 如果 PP 与 TuT_u 有交，显然 PP 不能经过 uu，所以 P∈TuP\in T_u，但由于选的是最深的 uu，此时必然有 dis(lca(P),u)≤ddis(lca(P),u)\leq d，矛盾。
  4. 如果 PP 与 TuT_u 无交，那么对于任意 x∈Tux\in T_u，xx 到 PP 上任意一点的路径都要经过 uu，所以 dis(x,P)≥dis(u,P)dis(x,P)\geq dis(u,P)，故不存在满足条件的 xx。
所以只需要检验 uu 是否合法即可。和上面类似还是考虑 v=anc(u,d)v=anc(u,d)，那么首先所有路径都要和 TvT_v 有交。接下来对路径 PP 的 lcalca 分类讨论一下：
  1. 如果 lca(P)∈Tulca(P)\in T_u，这个上面讨论过了，一定有 dis(u,P)≤ddis(u,P)\leq d。
  2. 如果 lca(P)lca(P) 在路径 (u,v)(u,v) 上，那么 dis(u,P)≤dis(u,lca(P))≤dis(u,v)≤ddis(u,P)\leq dis(u,lca(P))\leq dis(u,v)\leq d。
  3. 如果 lca(P)∉Tvlca(P)\notin T_v，由于 PP 和 TvT_v 有交，所以 PP 经过 vv，也有 dis(u,P)≤ddis(u,P)\leq d。
  4. 否则，lca(P)lca(P) 和 uu 没有祖先后代关系，此时有 dis(u,P)=dis(u,lca(P))dis(u,P)=dis(u,lca(P))，故条件等价于 dis(u,lca(P))≤ddis(u,lca(P))\leq d。
可以发现，对于前两种情况，也一定有 dis(u,lca(P))≤ddis(u,lca(P))\leq d，所以可以将条件转化为：
  1. ∀P∈S,P∩Tv≠∅\forall P\in S,P\cap T_v\neq \empty。
  2. ∀P∈S∧lca(P)∈Tv,dis(u,lca(P))≤d\forall P\in S\wedge lca(P)\in T_v,dis(u,lca(P))\leq d。
对于第一个条件，可以用树状数组维护树上差分解决。
对于第二个条件，实际上是要 uu 到所有在 vv 的子树内的 lca(P)lca(P) 的距离最大值。这就是前置结论中的问题，线段树维护点集直径即可。
树剖求 lcalca 可以做到 O(n+Qlog⁡2n)O(n+Q\log^2n)，转 RMQ\mathrm{RMQ} 用 st 表可以做到 O(nlog⁡n+Qlog⁡n)O(n\log n+Q\log n)。
求 FF 则是 O(n+Qlog⁡3n)O(n+Q\log^3n) 或 O(nlog⁡n+Qlog⁡2n)O(n\log n+Q\log^2n)。
提交记录（st 表和树剖差不多）。

解法二

上面的解法中我们将求 FF 通过二分转化为操作 3，现在反过来，求出 FF 后和 dd 比较来回答操作 3。
考虑一个特殊情况：所有路径都是单点。此时路径集 SS 变成了点集，那么就是求 F=min⁡x{max⁡u∈S{dis(x,u)}F=\displaystyle\min_x\{\max_{u\in S}\{dis(x,u)\}。对于每个 xx，要求它到点集 SS 的最大距离，那么由前置结论，求出 SS 的直径 (u,v)(u,v)，就有 F=min⁡x{max⁡{dis(x,u),dis(x,v)}F=\displaystyle\min_x\{\max\{dis(x,u),dis(x,v)\}。对于所有 xx 求最小值，那么取到最小的 xx 就应该是 (u,v)(u,v) 路径的中点，故 F=⌈dis(u,v)2⌉F=\lceil\frac{dis(u,v)}{2}\rceil。
现在 SS 中不是点而是路径，有什么区别呢？可以大胆猜想没有什么区别，记路径集直径 D(S)=max⁡P,Q∈S{dis(P,Q)}D(S)=\displaystyle\max_{P,Q\in S}\{dis(P,Q)\}，则 F=⌈D(S)2⌉F=\lceil\frac{D(S)}{2}\rceil。
设 SS 中距离最远的两条路径是 P,QP,Q，那么要证明上面这个结论，我们证明对于任意的点 xx，xx 到 SS 中路径的最远距离是：
{max⁡{dis(x,P),dis(x,Q)},D(S)>0dis(x,⋂p∈Sp),D(S)=0\begin{cases} \max\{dis(x,P),dis(x,Q)\}, &D(S)>0\\ dis(x,\bigcap_{p\in S}p), &D(S)=0 \end{cases}
即在 D(S)>0D(S)>0 时只需要考虑最远的两条路径，在 D(S)=0D(S)=0 时只需要考虑所有路径的交（此时这个交一定非空）。
先证明 D(S)>0D(S)>0 的情况，假设存在路径 RR，满足 dis(x,R)>dis(x,P),dis(x,Q)dis(x,R)>dis(x,P),dis(x,Q)，将路径 RR 作为树根，其他部分会形成若干子树，显然 xx 不在 RR 上，不妨 设 xx 在子树 uu 中，与 uu 相邻的 RR 上的点是 ff，则 dis(x,R)=dis(x,f)dis(x,R)=dis(x,f)。如下图： 接下来分类讨论有点多，建议画一张这种图以更好地理解：
  1. 若 P,QP,Q 中至少一条与子树 uu 无交（不妨设为 PP），那么从 xx 到 PP 上任何一点都要经过 (u,f)(u,f) 这条边，所以 dis(x,P)≥dis(x,f)dis(x,P)\geq dis(x,f)，矛盾；
  2. 若 P,QP,Q 中至少一条经过 uu（不妨设为 PP），那么显然 QQ 不经过 uu，所以 QQ 在 uu 子树内，此时 dis(R,Q)=dis(f,Q)>dis(u,Q)≥dis(P,Q)dis(R,Q)=dis(f,Q)>dis(u,Q)\geq dis(P,Q)，矛盾。
  3. 对于下面的几种情况，P,QP,Q 都在 uu 子树内，所以 dis(P,R)=dis(lca(P),f),dis(Q,R)=dis(lca(Q),f)dis(P,R)=dis(lca(P),f),dis(Q,R)=dis(lca(Q),f)。方便起见，记 p=lca(P),q=lca(Q)p=lca(P),q=lca(Q)。
    1. 若 p,qp,q 存在祖先后代关系（不妨设 pp 是祖先），那么有 dis(f,q)>dis(p,q)≥dis(P,Q)dis(f,q)>dis(p,q)\geq dis(P,Q)，矛盾；
    2. 当 p,qp,q 不存在祖先后代关系时，有 dis(P,Q)=dis(p,q)dis(P,Q)=dis(p,q)。
      1. 若 P,QP,Q 中有一个与路径 (x,u)(x,u) 有交（不妨设为 PP），那么 QQ 肯定与 (x,u)(x,u) 无交（否则会变成情况 4），那么此时 qq 为 xx 的后代或者没有祖先后代关系，所以有 dis(x,Q)=dis(x,q)dis(x,Q)=dis(x,q)，且 dis(x,P)≤dis(x,p)<dis(x,f)dis(x,P)\leq dis(x,p)<dis(x,f)。
        • 这时候考察点 xx 和点集 f,p,q{f,p,q}，由 dis(P,Q)≥dis(P,R),dis(Q,R)dis(P,Q)\geq dis(P,R),dis(Q,R)，得 dis(p,q)≥dis(p,f),dis(q,f)dis(p,q)\geq dis(p,f),dis(q,f)。
        • 那么由点到点集的最远距离的结论，有 max⁡{dis(x,p),dis(x,q)}≥dis(x,f)\max\{dis(x,p),dis(x,q)\}\geq dis(x,f)，这与 max⁡{dis(x,P),dis(x,Q)}≥dis(x,R)\max\{dis(x,P),dis(x,Q)\}\geq dis(x,R) 矛盾。
      2. 若 P,QP,Q 均和 (x,u)(x,u) 无交，那么和上面类似有 dis(x,P)=dis(x,p),dis(x,Q)=dis(x,q)dis(x,P)=dis(x,p),dis(x,Q)=dis(x,q)，会导出一样的矛盾。
上面的讨论覆盖了所有情况，故这部分得证。
对于 D(S)=0D(S)=0 的情况，可以归纳变成只有两条路径的情况，设为 P,QP,Q，记 R=P∩QR=P\cap Q。如下图： 可以发现本质上 xx 所在的子树只有三种不同情况：接在 P∖RP\setminus R 上、接在 Q∖RQ\setminus R 上、接在 RR 上。分别讨论不难证明。
剩下的问题就是要维护最远的 P,QP,Q 或所有路径的交。求出两条路径的距离或者交可以根据四个端点两两的 lcalca 分类讨论得到。对于路径之间的距离，有和上面类似的结论：任意的路径 pp，pp 到 SS 中路径的最远距离是：
{max⁡{dis(p,P),dis(p,Q)},D(S)>0dis(p,⋂q∈Sq),D(S)=0\begin{cases} \max\{dis(p,P),dis(p,Q)\}, &D(S)>0\\ dis(p,\bigcap_{q\in S}q), &D(S)=0 \end{cases}
证明也差不多。所以可以类似线段树维护点集直径用线段树维护路径集直径。
用 st 表求 lcalca 复杂度 O((n+Q)log⁡n)O((n+Q)\log n)。
求 FF 比较有优势，在这个题上没有。
提交记录。

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...