洛谷 P8176 题解

璀璨星空1 · 2023-06-20 22:55:27 · 题解

upd：之前加粗的 markdown 挂了。

尘沙里稀疏的草和木凋零朽枯
他在我的耳边计算着明天的路途

至今为止我做过最困难的一道思维题。定数 \bold{\texttt{Lv}\ 18} 应该没有问题。

第 1 部分：结论 1\sim3。

称一个点染 1 指这个点上有水井，染 0 指这个点上无水井。称一条长度为 k-1 的路径为一个旅行。

我们主要分析一个合法染色方案需要满足的性质。我们将推导出 10 条结论，随着结论的推导揭示我们的做法。

结论 1. 若两个点 u,v 满足 \text{dis}(u,v)=k，则 \text{col}(u)=\text{col}(v)。

先 DFS 两遍求出树的一条直径 p\sim q。

• 若 \text{dis}(p,q)<k-1，则不存在任何可能的旅行。此时答案 =2^n。先把这种情况判掉。

• 若 \text{dis}(p,q)\geq k-1，则树的直径恰有 k 种染法。对于每个 i，从 p 到 q 数第 i,i+k,i+2k,\cdots\cdots 个点的 \text{col} 必须都相同。记只将第 i 个等价类染 1 的染法为第 i 种染法。

我们将 p\sim q 上的每个点拿出来，以它们为根向远离直径的方向 DFS 这棵树。我们预处理出一些信息。记 \text{project}(u) 为 u 到 p\sim q 上的投影，记 \text{dep}(u) 表示以 \text{project}(u) 为根 u 的深度，再记 h_u 为 u 子树的高度，即 u 子树内最深的点 v 的 \text{dep}(v)-\text{dep}(u)。

结论 2. 对于任意一个点 u，\max\limits_{i=1}^n\text{dis}(u,i)=\max\big\{\text{dis}(u,p),\text{dis}(u,q)\big\}。

结论 3. 不需要考虑那些经过直径但两个端点都不在直径上的旅行 u\sim v。若其他所有旅行都满足要求，则这些旅行一定满足要求。

结论 3 是此题的关键结论。设 u 在 v 的左侧。因为 p\sim q 是直径，一定存在两个直径上的点 u',v' 分别在 \text{project}(u) 和 \text{project}(v) 的左侧和右侧，使得 \text{dis}\big(u',\text{project}(u)\big)=\text{dep}(u) 且 \text{dis}\big(v',\text{project}(v)\big)=\text{dep}(v)。那么 u'\sim v'，u'\sim v 以及 u\sim v' 都是旅行。如果它们都满足要求，则 \text{sum}(u,v)=\text{sum}(u',v)+\text{sum}(u,v')-\text{sum}(u',v')=1+1-1=1，因此 u\sim v 也满足要求。

第 2 部分：结论 4\sim8。

但还有一种旅行 u\sim v 是不经过直径的，与直径没有交点。先假设不存在这样的旅行。注：以下 u,v 都默认不在直径上。

结论 4. 若叶子 u 满足 h_u+\text{dis}(u,p)<k-1 且 h_u+\text{dis}(u,q)<k-1，则任何可能的旅程都不包含 u。将 u 删去并将答案 \times2。

结论 5. 若结点 u 满足 \text{dis}(u,p)\geq k-1 或 \text{dis}(u,q)\geq k-1，则 u 处在某个等价类中。称这样的结点 u 是有归属的，否则是无归属的。

• 若 \text{dis}(u,p)\geq k-1，则 \text{class}(u)=\text{dis}(u,p)\bmod k。
• 若 \text{dis}(u,q)\geq k-1，则 \text{class}(u)=\big(\text{dis}(p,q)-\text{dis}(u,q)\big)\bmod k。

结论 6. 若结点 u 满足 h_u+\text{dis}(u,p)\geq k-1 且 h_u+\text{dis}(u,q)\geq k-1，则称 u 是两侧点，否则称 u 是一侧点。

• 两侧点 u 的父亲 \text{Fa}(u) 一定也是两侧点。因为 \text{dis}(u,p),\text{dis}(u,q) 都只会减小 1，但是 h_u 至少会增加 1。
• 因此，所有的一侧点构成若干棵子树。将这些子树的根拿出来，称这些点为关键点。

结论 7. 若结点 u 的子树内存在 v 使得 \text{dis}(v,p)\geq k-1 且 \text{dis}(v,q)\geq k-1 且 \text{dep}(v)\leq\left\lfloor\dfrac{k-1}2\right\rfloor，则 u 必须染 0。

• 因为 v 满足这 3 个条件，一定存在两个直径上的点 p',q' 分别在 \text{project}(u) 的左侧和右侧，使得 \text{dis}(v,p')=\text{dis}(v,q')=k-1。
• 假如 u 染 1 的话，直径上 p'\sim q' 必须全都染 0，这是连续 2k-2\text{dep}(v)-1\geq2k-(k-1)-1=k 个全都染 0 的点，矛盾！

结论 8. 若结点 u 是两侧点，则要么 u 是有归属的，要么 u 必须染 0。

结论 8 是此题的关键结论。在某种意义上，结论 4\sim 7 都是为结论 8 服务的。

• 若 \text{dep}(u)>\left\lfloor\dfrac{k-1}2\right\rfloor，则 \text{dis}(u,p)\geq2\Big(\left\lfloor\dfrac{k-1}2\right\rfloor+1\Big)\geq k，\text{dis}(u,q) 同理。因此 u 是有归属的。

• 若 \text{dep}(u)\leq\left\lfloor\dfrac{k-1}2\right\rfloor，不妨设 \text{dis}(u,p)\geq\text{dis}(u,q)。因为 u 是两侧点，这意味着 u 的子树内存在 v 使得 \text{dis}(v,q)\geq k-1。考虑最浅的那个 v，有 \text{dep}(v)=k-\text{dis}(\text{project}(u),q)-1。由于 \text{dep}(v)\leq\text{dis}(\text{project}(u),q)，因此 \text{dep}(v)\leq\left\lfloor\dfrac{k-1}2\right\rfloor。

要么 u 是有归属的，要么 u 必须染 0。因为二者的判别是根据 \text{dep}(u) 是否 >\left\lfloor\dfrac{k-1}2\right\rfloor，所以这个结论很有用。

第 3 部分：结论 9\sim10。

现在考虑一侧点构成的子树的根（即关键点）u，\text{Fa}(u) 要么在直径上要么为两侧点。不妨设 \text{dis}(u,p)\geq\text{dis}(u,q)。

结论 9. 若结点 u 被一条长度 \geq k-1 的路径 p'\sim q' 包含，且 p'\sim q' 上存在一个点 v 已经确定染 1，则 u 染 0 还是 1 也已经确定。

• 若 \text{dis}(u,v)\bmod k=0，则 u 必须染 1。否则 u 必须染 0。

因此若 p\sim\text{Fa}(u) 中存在 1，则 u 子树内的染色方案已经唯一确定。

反之若 p\sim\text{Fa}(u) 全都染 0，则需要给 u 的子树染一个极小割。即 u 的子树内染 1 的结点 v 一定满足 \text{dis}(v,p)\leq k-1，并且子树内所有的叶子 v 都满足 v 到 u 的路径上恰有一个染 1 的结点。我们记这个为 F_u，F_u 可以通过 DP 直接求出。

再去掉不一定成立的假设，考虑存在不经过直径的旅行 u\sim v 时的情况。

结论 10. 若旅行 u\sim v 与直径无交，那么 u\sim v 上的所有点都是两侧点。

• 在同一个 \text{project}(u) 下 \text{dis}(u,p)=\text{dep}(u)+\text{dis}\big(\text{project}(u),p\big)，因此 \text{class}(u) 是仅关于 \text{dep}(u) 的斜率 =\pm1 的一次函数。我们只需要 DFS 每个两侧点 u，并得到 u 的所有子树的高度的最大值和次大值即可。

最后，我们来简略的叙述我们的做法。具体实现可以看下方的代码链接，代码和题解叙述的逻辑是完全一致的。

我们维护两个长度为 k 的序列 \text{ok}(i) 和 \text{ans}(i) 分别表示第 i 种染法是否可行以及其合法方案数，初始值为全 1。

1. 对于每个关键点 u，u 的子树对 \text{ans}(i) 的贡献是一个区间乘的形式。

   考虑什么时候 p\sim\text{Fa}(u) 会全都染 0。p\sim\text{Fa}(u) 都要么在直径上要么为两侧点，因此它们都要么是有归属的，要么必须染 0。

   取出 p\sim\text{Fa}(u) 上所有有归属的点的 \text{class} 值构成的集合 S。假设我们采用第 i 种染法，那么如果 i\not\in S，p\sim\text{Fa}(u) 就会全都染 0。

   于是我们要对所有的 i\not\in S 将 \text{ans}(i) 乘上 F_u。我们将 p\sim\text{Fa}(u) 拆成 p\sim\text{project}(u) 和 \big(\text{project}(u),\text{Fa}(u)\big] 两个部分。那么每个部分内的 S 分别构成一段区间。

   进一步的观察表明需要区间乘的 \mathcal{O}(1) 个区间的右端点 r\in\Big\{k-1,\left\lfloor\dfrac{k-1}2\right\rfloor\Big\}，因此可以直接打后缀乘标记，不需要求乘法逆元。

2. 对于每个两侧点 u，考虑 u 向 p 方向延伸出的长度为 k-1 的链。取出它的集合 S，则在 S 中出现 0 次或 2 次的 i 将会被 \text{ban} 掉。这将会 \text{ban} 掉 \mathcal{O}(1) 个区间，直接差分即可。u 向 q 方向延伸出的链同理。

3. 对于每个两侧点 u，求出 u 的所有子树的高度的最大值 f 和次大值 s。若 f+s\geq k-1，则需要考虑以 u 为 \text{LCA} 的与直径无交的旅行。其中限制最严的一个较短子树的高度是 \min\Big\{s,\left\lfloor\dfrac{k-1}2\right\rfloor\Big\}，取出它的集合 S，相应 \text{ban} 掉 \mathcal{O}(1) 个区间。

最终把还活着的 \text{ans}(i) 加起来即可。时间复杂度 \mathcal{O}(n)，空间复杂度 \mathcal{O}(n)。代码链接：https://loj.ac/s/1799853。