自动搬运

查看原文

来自洛谷，原作者为

	璀璨星空1 倘若我们义无反顾去做不可能之事，世上便再没有不可能。

搬运于2025-08-24 22:36:37，当前版本为作者最后更新于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。