Graphs & Trees

· · 算法·理论

由于被 CSP-S 的三道图论题 创 死 ，所以决定来写这个东西。

比隔壁 wwh 的 dp 题单简单多了。

有手就行。

贪心/构造相关

CF723E One-Way Reform

Difficulty : 2200

Description

给出一个 n 个点 m 条边的无向图，你需要给每条边定向，使得有尽量多的点，入度等于出度，并构造方案。 \sum n\le 200。

Solution

首先度数为奇数的点当然是不可能放进答案里的，所以答案的上限为 \sum\limits_{i=1}^{n}[2\mid d(i)]，即偶度点的个数。

下面考虑构造合法的解，使得每一个偶点都满足条件。

新建一个虚点，向每个度数为奇数的点连无向的虚边，把原图补全成一个每个点的度数都是偶数的无向图。这种图中必定有欧拉回路。

方案就是根据回路的顺序给边标方向，然后把刚刚添加的虚边删掉。我们发现每个偶点都没有连虚边，所以它们的出度均等于入度，构造完毕。

CF1062E Company

Difficulty : 2300

Description

给定一颗树，有若干个询问，每个询问给出 l，r，要求编号为 l~r 的点任意删去一个之后剩余点的 LCA 深度最大，输出删去点的编号和 LCA 的最大深度。

#### Solution 对于一个询问 $[l,r]$，假设 $lca(l,l+1,...,r)=u$。 如果删去了点 $x$，使得 $lca$ 从 $u$ 下移到了点 $v$，说明 $x$ 一定在 $u$ 的子树内并且不在 $v$ 的子树内。 这样顺序好像不太对，这样说吧： 如果你想让答案从 $u$ 变成 $v$，那么你需要尽可能选一个**不在 $v$ 子树内的点**。 不难发现，取一个 $[l,r]$ 中 `dfs` 序的最小，或者取个最大，答案就这两种情况，不可能更优了。 因为如果能到 $v$ 的话，如果 $v$ 的 `dfs` 序在中间，那你取最小和最大都行；如果 $v$ 的 `dfs` 序在两边，那总有一边是不在 $v$ 的子树里的。 于是取 $[l,r]$ 中 `dfs` 序最小/最大然后取深度 $\max$ 即可。 复杂度 $O(n\log^2 n)$。 ### [P5631 最小mex生成树](https://www.luogu.com.cn/problem/P5631) #### Description 给定 $n$ 个点 $m$ 条边的无向连通图，边有边权。 设一个自然数集合 $S$ 的 $\text{mex}$ 为：最小的、没有出现在 $S$ 中的自然数。 现在你要求出一个这个图的生成树，使得其边权集合的 $\text{mex}$ 尽可能小。 $n\le 10^6,m\le 2\times 10^6$。 #### Solution 经典线段树分治。 考虑如何判断能否让 $x$ 成为答案，把所有权值为 $x$ 的边删掉后，若图联通则有生成树，这样的生成树的边中一定不包含权值 $x$。所以这个图联通是 $x$ 可以为答案的**必要条件**。 显然只要 $1\to x-1$ 都不能成为答案，那么满足上述必要条件即为最小的 $\text{mex}$ 值。 于是可以考虑线段树分治，当前分治区间 $[l,r]$ 表示权值在 $[l,r]$ 之间的边都不加进图里。使用可撤销并查集维护，优先跑左区间即可。 ### [ARCLC Diverta City](https://www.luogu.com.cn/problem/AT_diverta2019_2_f) Difficulty : 3300 #### Description # Diverta City 构造一张 $n$ 个点的无向完全图,使得所有的 $\frac{n!}{2}$ 条哈密顿路径的边权和互不相同。要求所有边权都是正数,且任意哈密顿路径的边权和不超过 $10^{11}$。 $2 \leq n \leq 10$。 先冷静思考一下，$n$ 个点的无向完全图的哈密顿路径数为啥是 $\frac{n!}{2}$？ 事实上，可以考虑归纳证明。 - $n=2$ 时，哈密顿路径数为 $1$。显然满足。 - $n=k$ 时，若哈密顿路径数为 $\frac{k!}{2}$，下证 $n=k+1$ 时，哈密顿路径数为 $\frac{(k+1)!}{2}$。 考虑 $k$ 个点的完全图，我们在其中插入一个点 $k+1$。随便拉出原图的一个哈密顿路径，这样的路径有 $\frac{k!}{2}$ 种，假设为 $P:\{u\to v\}$，考虑新生成哈密顿路径 $P'$ 的方式（**记住这些方式，下面构造的证明要用到**）： - $k+1$ 可以插到 $v$ 后面变成路径的末尾，即 $P':\{u\to v\to k+1\}$。 - $k+1$ 可以插到 $u$ 前面变成路径的首位，即 $P':\{k+1\to u\to v\}$。 - 找到路径中间的一条边 $w:i\to j$，这样的边有 $k-1$ 条，我们把这条边从 $P$ 中删去，用 $i\to k+1$ 和 $k+1\to j$ **替换**。即 $P':\{u\to k+1\to v\}$。 根据一条原有的路径新生成哈密顿路径的方案数为 $1+1+(k-1)=k+1$ 种，那么新生成哈密顿路径的条数就是 $\frac{k!}{2}\cdot (k+1)=\frac{(k+1)!}{2}$。归纳得证。 --- ~~然而这个结论对这道题并没有什么用~~这启示我们归纳构造。显然 $n=2$ 时我们直接将 $1$ 和 $2$ 之间连权值为 $1$ 的边即可。考虑 $n=k$ 时我们构造出了合法的完全图，考虑插入 $k+1$ 点： 将此时**边权和最大**的哈密顿路径的边权和记为 $M$，假如我们现在构造出一个序列 $a$ 满足： - $\forall 1\le i<j\le k,a_i\neq a_j

那么我们就可以将 k+1 向 1\le i\le k 的 i 连权值为 (M+1)a_i 的边。我们把这样的边叫做新边。

这样的图是一定合法的，因为考虑一条新的哈密顿路径仅会经过新的边 1 或 2 次，而由于 M 的最大性，属于旧哈密顿路径的边边权和不超过 M，而 a 中任意至多 2 个数的和都至少差 1，那么：

所以问题来到如何构造一个满足条件的序列 a，随便搜一下即可。构造出的 a 形如 \{1,2,4,7,12,20,29,38,52,73\}。

然后我们需要求一张完全图的哈密顿路径边权最大和，也是随便搜一下即可。发现构造出来的图刚好在给定的范围之内，就做完了。

拓扑排序相关

CF1100E Andrew and Taxi

Difficulty : 2200

Description

给定一个有向图，改变其中某些边的方向，它将成为一个有向无环图。现在求一个改变边方向的方案，使得所选边边权的最大值最小。

Solution

一眼鉴定为二分答案。

考虑当前二分一个 x，权值小于等于 x 的边都可以反向，但是大于 x 的边都不能动。

那就先把 w_i>x 的边 i 全部加进图中，如果产生了环就必定不行。

如果此时没有环，那么加进 \le x 的边后就必定可以构造方案使得图中无环。

因为如果有环的话，这个环必定包含若干 \le x 的边，把这些边中任选一条反向即可。对于若干个环我们总有反向的方案。

那考虑一条边什么时候需要反向：由于所有 >x 的边组成的图必然是 DAG，那么我们对其求出拓扑序。如果 \le x 的边中有 (u,v) 使得 u 的拓扑序比 v 的大，那么说明组成了环，我们将它反向即可。

时间复杂度 O((n+m)\log w)。

AGC027F Grafting

Difficulty : 3544

Description

给定两棵 n 个节点的树 A,B, 你需要对 A 执行若干次操作, 每次操作选择一个叶子节点, 删除连接这个叶子的边，并将这个叶子节点连向任意一个另外的点, 每个点只能被选择一次。

Solution

鬼知道这是什么难度评分。

首先如果一开始 A 和 B 相同，可以直接输出 0。

否则 O(n^2) 枚举一个被操作的叶子 x，和 x 接到了的 y 点，此时 x 不能再被操作，所以将其当作新树 A' 和 B 的根节点。

由于操作是作用于叶子的，所以一个非叶节点想要被操作，当且仅当其所有后辈节点都被扔出去了。反之，如果不操作一个点 u 的话，u 的祖先也不会被操作。

如果需要操作一个点 u，说明 u 在 A' 和 B 中的父亲不同，因为你断开再连回去显然不优。如果 u 在 A' 和 B 中的父亲不同，那么你也一定要操作这个点，所以这是充分必要的。

根据上面那个结论，可以知道每个点需不需要被操作。由于操作顺序从叶子到根，所以如果存在一个点 u，其在 A' 中的父亲 \text{fa}_{A',u} 需要被操作，但是 u 不能被操作，那么就无解了。

否则把所有需要操作的 u 找出来，如果其 A' 中的父亲 \text{fa}_{A',u} 需要被操作，那么 u 操作的顺序一定比 \text{fa}_{A',u} 前；如果其 B 中的父亲 \text{fa}_{B,u} 需要被操作，那么 u 操作的顺序一定在 \text{fa}_{B,u} 后。建图 O(n) 跑拓扑序即可，如果无环即有解，为需要被操作的点数加上你枚举的那个叶子 x。

复杂度 O(Tn^3)。

AGC010E Rearranging

Difficulty : 3887

Description

有一个 n 个数组成的序列 a_i。

高桥君会把整个序列任意排列，然后青木君可以进行任意次操作，每次选择两个相邻的互质的数交换位置。

高桥君希望最终序列的字典序尽量小，而青木君希望字典序尽量大。求最终序列。

Solution

这又是什么鬼评分。

考虑先手操作完后得到的序列为 b_i，后手如何操作得到最大答案。

由于不互质的数不能交换，所以任意一对 i<j,\text{gcd}(b_i,b_i)=1，后手操作后相对顺序不变。

所以可以枚举每对不互质的数，编号小的往大的连边，然后用优先队列跑最大拓扑序。

再考虑先手如何操作。

容易发现相当于是再一个无向图上确定每条边的方向，使其成为一个 \text{DAG}，并且最大拓扑序最小。

贪心先从小的数开始连边即可。

复杂度 O(n^2\log n)。

最短路相关

USACO08JAN Telephone Lines S

Description

给定一个无向图 G=(V,E)，边 e\in E 带权，求一条 1 到 N=|V| 的路径，使得路径上第 k+1 大值最小。N\le 10^3,|E|\le 10^4,w\le 10^6。

Solution

还是二分答案 x。

新建一个图，边还是原来的边，但如果边权 \le x 的话，把它的边权改为 0，否则为 1，跑 1 到 N 的 01 最短路判断是否小于等于 k 即可。

时间复杂度还是 O((n+m)\log w)。

小清新。

网络流相关

\text{最大流\ =\ 最小割} \text{二分图最小点覆盖\ =\ 二分图最大匹配数} \text{一般图最小路径覆盖数\ =\ 点数\;-\;最大独立集\ =\ 点数\;-\;转换成二分图后的最大匹配数（最小割）\;}

USACO05JAN Muddy Fields G

Description

牧场是一个 R \times C 的矩形，包含泥地和草地，其中 1 \leq R,C \leq 50。约翰决定在泥泞的牧场里放置一些木板，每一块木板的宽度为 1 个单位，长度任意，每一个板必须放置在平行于牧场的泥地里。 使用最少的木板覆盖所有的泥地。一个木板可以重叠在另一个木板上，但是不能放在草地上。

Solution

考虑如果是横着放的话，必定包含了这一行的极长泥地子段，不然必定不优。竖着放同理。

所以先预处理出对于每个泥地，被横着覆盖的木板的编号或者被竖着覆盖的木板的编号。

例如样例：

原   横   竖
4 4  4 4  4 4
*.*. 1020 1040
.*** 0333 0345
***. 4440 2340
..*. 0050 0040

然后把每个泥地当作边，建二分图，左部为行，右部为列。

如果一个点为泥地，那么覆盖它的行的编号向覆盖它的列的编号连边。

答案即最小点覆盖等于最大匹配，网络流即可。由于点数最多 O(n^2)，边数最多 O(n^2)，于是时间复杂度 O(n^3)，然而根本跑不满。

ARC074D Lotus Leaves

Description

给定一个H×W的网格图，有的点可以踩，有的不能，因为有障碍。

现有一人在 S 处，向 T 移动，若此人现在在 (i,j) 上，那么下一步他可以移动到 (i,k),k\in[1,W] 或 (k,j),k\in[1,H] 上。可以跨越障碍。

问最少需要再放置多少障碍，可以使这个人无法从 S 到达 T，输出最少的数目；如果无论如何都不能使这个人无法从 S 到 T，则输出 -1。

Solution

如果网格只是 4 联通的话，似乎就是最小割板子了（当然也有不用最小割的做法）。

然后考虑一行一列相互连通怎么做，有一个套路叫网格图转二分图。

因为我们可以将一行或一列看成联通的整体，所以建一个二分图，左边表示 1 到 n 行，右边表示 1 到 m 列。

两个点之间有连边时可以看作联通，那么不难看出我们要求的就是原图的最小割。

跑最大流即可。

POI2010 MOS-Bridges

Description

给定一个图，边有权值且正着走和逆着走有不同权值，在这个图上求一条最大边权最小的欧拉回路，从点 1 出发，要求输出方案。

第一行包括两个整数 n 和 m，分别代表点的个数和边的个数。接下来 m 行每行包括 4 个整数 a,b,l,p，分别代表边的两个端点和正着走的权值和逆着走的权值。

如果没有符合要求的路径输出 NIE，否则输出两行。第一行一个整数表示最小的权值，第二行 m 个整数表示依次经过的边的编号。

Solution

其实这题有两种建模方法，因为我都写了，所以两个都讲好了。

一眼二分答案，转为判定性问题：

给定含有无向边和有向边的图 G，判断是否存在欧拉回路。

首先先判掉存在 u，2\nmid \text{deg}_u 的情况。

不能简单地根据度数判断，考虑网络流建模。

考虑到对于每条边 e_i，最多给一个点会提供 1 的出度。

然后对于一个点 v_i，最后它的出度一定为 \frac{\text{deg}_{v_i}}{2}。

这启示我们将边和点两两匹配。那我们对于 S\to e_i，连流量为 1 的边，表示这条边最多匹配 1 个点给出度。对于 v_i\to T，连流量为 \frac{\text{deg}_{v_i}}{2} 的边，表示这个点要匹配这么多条边给它出度。对于一条边 e_i=(u,v)，如果单向，不妨设 u\to v，那么直接 e_i 向 u 流 1。否则 e_i 向 u,v 分别流 1，表示 e_i 既可以匹配 u，也可以匹配 v。

然后我们跑最大流，判断是否满流即可。最后构造方案可以在残量网络上根据是否有 e_i\to u_i 建图跑欧拉回路。

先给每条无向边随意定一个方向，假定是 u\to v，计算此时每个点的入度 \text{in}_u 和出度 \text{out}_u。

那么对于 \text{in}_u>\text{out}_u 的点，我们将 S 向 u 连流量 \frac{\text{in}_u-\text{out}_u}{2} 的边。表示它需要流入这么多流量才能使 \text{in}_u=\text{out}_u。

同理，对于 \text{in}_v<\text{out}_v 的点，我们将 v 向 T 连流量 \frac{\text{out}_v-\text{in}_v}{2} 的边。表示它需要流出这么多流量才能使 \text{in}_v=\text{out}_v。

对于无向边 (u,v)，我们假定了 u\to v。那么 v\to u 连一条流量为 1 的边，表示我们可以反悔。

然后同样跑最大流，判断是否满流，然后构造有向图跑欧拉回路即可。

连通性相关

CF1137C Museums Tour

Difficulty : 2500

Description

一个国家有 n 个城市，通过 m 条单向道路相连。有趣的是，在这个国家，每周有 d 天，并且每个城市恰好有一个博物馆。

已知每个博物馆一周的营业情况（开门或关门）和 m 条单向道路，由于道路的设计，每条道路都需要恰好一个晚上的时间通过。你需要设计一条旅游路线，使得从首都：1 号城市开始，并且当天是本周的第一天。每天白天，如果当前城市的博物馆开着门，旅行者可以进入博物馆参观展览，否则什么也做不了，这一天的晚上，旅行者要么结束行程，要么通过一条道路前往下一个城市。当然，旅行者可以多次经过一个城市。

要求让旅行者能够参观的不同博物馆数量尽量多（同一个城市的博物馆参观多次仅算一次），请你求出这个最大值。

#### Solution 考虑拆点，把城市 $u$ 拆成 $(u,t)$，$t\in [0,d)$， 表示一周的第 $t$ 天在 $u$，如果 $u$ 能到 $v$，那 $(u,t)\to (v,t+1\mod d)$。$(u,t)$ 的权值为 $1$ 当且仅当 $u$ 的博物馆在第 $t$ 天开门了，否则为 $0$。 注意到一开始从 $(1,0)$ 出发，某条路径能够到达的所有点的权值之和的最大值即为答案，但是不可算重。 由于不能算重，我们使用 `tarjan` 缩点，显然如果旅行者进入了某个 `scc`， 那这个 `scc` 里面所有点的权值都可以被算到。缩完点后原图变成了一个 `DAG` ，于是直接跑最长路 dp 即可。 ### [ZJOI2007 最大半连通子图](https://www.luogu.com.cn/problem/P2272) #### Description 一个有向图 $G=(V,E)$ 的半联通子图定义为：图 $G$ 的子图 $G'=(V',E')\subseteq G$， $\forall u,v\in V',s.t.\ u\to v/v\to u$，即 $u$ 能到 $v$ 或 $v$ 能到 $u$。 给定一张有向图 $G$ ，求 $G$ 中最大半联通子图，即 $|V'|\to \max$，的大小与个数。 #### Solution 考虑 `tarjan` 缩点。 显然对于一个 `scc`，要么全部取，要么全部不取。把每个 `scc` 缩成点，点权为这个强连通分量的大小。 剩下来一张 `DAG`，我们发现最大半联通子图的大小就是 `DAG` 上带权最长链的大小，类似上一题最长路 dp 即可。 统计方案的话，可以在 dp 时顺便更新。 ### [CF1361E James and the Chase](https://www.luogu.com.cn/problem/CF1361E) Difficulty : 3000 #### Description 给定一个有 $n$ 个点 $m$ 条边的**有向强连通图**。称一个点是**好的**当且仅当它到其他点都有且只有一条**简单路径**。如果好的点至少有 $20\%$ 则输出所有好的点，否则输出 `-1`。 $\sum n\leq 10^5,\sum m\leq 2\times 10^5$。 #### Solution 考虑给你一个点 $u$，如何判断其是否是好的。 那很简单是吧，只要以 $u$ 为根建出 `dfs` 树，没有**横叉边**或者**前向边**的话 $u$ 即为好节点。 那我们就可以 $O(n)$ 判断了。 如果我们现在知道一个点 $u$ 是好的，我们考虑如何求出所有的好节点。 还是以 $u$ 为根建出 `dfs tree`，考虑某个 $v$ 的子树，由于整个图的强连通性， $v$ 的子树中有连向其祖先的返祖边。我们不难发现这样的边有且仅有一条，否则 $v$ 有两条路径可以到达 $fa_v$ 即 $v$ 的父亲节点。 那我们先把所有子树 $v$ 内返祖到根的祖先的边的个数记下来，如果这个个数 $\ge 2$，排除 $v$ 是好点的可能，否则就顺便记下每个 $v$ 子树的那条返祖边指向的点。 假设 $v$ 的子树这条返祖边指向了 $w$，那么 $v$ 是好点，当且仅当 $w$ 是好点。考虑证明： - 如果 $w$ 是好点，那么 $w$ 到所有点路径唯一，又由于 $v$ 过 $w$ 出子树的路径是唯一的，所以 $v$ 到所有点的简单路径是唯一的，即 $v$ 是好点。 - 如果 $v$ 是好点，那么 $v$ 到所有点路径唯一，由于 $v$ 出子树必须要经过 $w$，所以 $w$ 到 $v$ 子树外所有点的路径也是唯一的，然后 $w$ 到 $v$ 的子树内的简单路径也是唯一的（没有前向边与横叉边），所以 $w$ 是好点。 所以综合所有的结论： 一个点 $v$ 是好点，当且仅当 $v$ 的子树内有且仅有一条连向 $v$ 的祖先的返祖边，并且这条边所连向的点是好点。 第一个条件可以考虑所有返祖边 $(a,b)$，它对哪些 $v$ 的子树内返向 $v$ 祖先的边的数量的有贡献。显然这样的 $v$ 分布在 $a\to fa_a\to...\to son_b$ 上，这里的 $son_b$ 为 $b$ 的儿子节点中靠近 $a$ 侧的那个，树上差分即可和第二个条件一起解决。 以上前提为 `dfs tree` 的根节点为好点。 那我们只要找到一个好点，并将其作为根节点，我们就能在 $O(n)$ 的范围内求解。 由于题目只要求好点数量大于等于 $20\%$ 时输出，所以我们随机取 $100$ 个点跑 $O(n)$ 判断。 如果好点数量不小于 $20\%$，你判断不出来的概率为 $\Big(\dfrac{4}{5}\Big)^{100}$ 趋近于 $0$。 所以随机跑 $100$ 次之后得不到一个好点的话就直接输出 $-1$，如果错了就是宇宙射线影响。 否则以找到的好点为根 $O(n)$ 求答案即可。 ## 计数相关 ### [AGC043C Giant Graph](https://www.luogu.com.cn/problem/AT_agc043_c) #### Description 给定三个简单无向图 $G_1,G_2,G_3$ ，其中每个图的点数均为 $n$，边数分别为 $m_1,m_2,m_3$。 现在根据 $G_1,G_2,G_3$ 构造一个新的无向图 $G$。$G$ 有 $n^3$ 个点，每个点可以表示为 $(x,y,z)$，对应 $G_1$ 中的点 $x$，$G_2$ 中的点 $y$，$G_3$ 中的点 $z$。边集的构造方式如下： 若 $G_1$ 中存在一条边 $(u,v)$，则对于任意 $1\le a, b\le n$，在 $G$ 中添加边 $((u,a,b),(v,a,b))$； 若 $G_2$ 中存在一条边 $(u,v)$，则对于任意 $1\le a, b\le n$，在 $G$ 中添加边 $((a,u,b),(a,v,b))$； 若 $G_3$ 中存在一条边 $(u,v)$，则对于任意 $1\le a, b\le n$，在 $G$ 中添加边 $((a,b,u),(a,b,v))$. 对于 $G$ 中的任意一个点 $(x,y,z)$，定义其点权为 $10^{18(x+y+z)}$。 试求 $G$ 的最大权独立集的大小模 $998244353$ 的值。 $2\le n\le 10^5, 1\le m_1,m_2,m_3\le 10^5$。 #### Solution 由于 $10^{18}$ 远大于 $n$，我们可以贪心地选择 $x+y+z$ 尽量大的点。于是我们将 $x+y+z\le x'+y'+z'$ 的 $(x,y,z)$ 向 $(x',y',z')$ 连**有向边**。 考虑一个 $\text{dp}$，令 $f_{x,y,z}$ 表示是否选择 $(x,y,z)$ 这个点，是则为 $1$，否则为 $0$。 显然有 $f_{x,y,z}=\prod\limits_{(x,y,z)\to (x',y',z')}[f_{x',y',z'}=0]$，即如果一个点的后继都不被选，我们就可以贪心地选择这个点；如果一个点地后继中有被选的，那这个点就不能被选。 这东西显然就是个博弈图。$f_{x,y,z}$ 为 $0$ 就是必胜态，$1$ 为必败态。于是我们需要选择所有处于**必败态**的点的权值。 容易发现，这就相当于在三个图上，分别有一个点，为 $x,y,z$，每次选择 $x,y,z$ 中的一个沿着有向边移动，不能移动的人输。三个图的 $\text{SG}$ 值异或起来为 $0$ 的话在原图上就是必败态了。 由于 $\text{DAG}$ 上 $\text{SG}$ 值不超过 $O(\sqrt n)$，可以 $O(n)$ 枚举两个图的 $\text{SG}$ 值 $i,j$，另一个图取 $\text{SG}$ 值为 $i\oplus j$ 的点即可。 ### [CF718E Matvey's Birthday](https://www.luogu.com.cn/problem/CF718E) Difficulty : 3300 #### Description 给定一个仅包含 `a`~`h` 的字符串。 有一个 $n$ 个结点的无向图，编号为 $0$ 到 $n−1$。结点 $i$ 与结点 $j$ 间有边相连当且仅当 $|i-j|=1$ 或 $S_i=S_j$。 求这个无向图的直径和有多少对点间的最短距离与直径相同。 #### Solution 不难发现答案 $\le 15$，极限的情况大概就是 $aabbcc...gghh$，此时跳一步和走一步等效。 这启示我们固定点 $i$，统计 $d(i,j)=D,j<i$ 的 $j$ 的个数，拆成 $i-j\le 15$ 的贡献和 $i-j>15$ 的贡献。 为了方便，以下称从 $i$ 到 $i+1$ 或 $i-1$ 为「走」，在相同颜色的点之间移动为「跳」。对于既可能拥有「走」操作有可能拥有「跳」操作的移动过程，称之为「跑」。 ##### $i-j\le 15$ 的贡献 一种情况是 $j$ 直接走到 $i$，步数为 $i-j$。 另一种情况是 $j$ 先跑到一个点 $k$，然后 $k$ 再跳到和它相同颜色的点 $l$，再由 $l$ 跑到 $i$，即 $j\to k\to l\to i$。 为了方便，预处理出 $f_{i,c}$ 表示 $i$ 跑到任意一个颜色为 $c$ 的点的最短距离，$g_{c_1,c_2}$ 为任意两个颜色分别为 $c_1,c_2$ 的点之间，$c_1$ 跑到 $c_2$ 的最短距离。由于边权相同，可以 bfs 求出。 于是 $j\to k\to l\to i$ 的最小步数为 $\min\limits_{c}\{f_{j,c}+f_{i,c}+1\}$。 两种情况取 $\min$ 即可算出 $j\to i$ 的最短距离。枚举 $i$，枚举前 $15$ 个数即可，复杂度 $O(15n)$。 ##### $i-j>15$ 的贡献 只有可能是 $\min\limits_c\{f_{j,c}+f_{i,c}+1\}$。但是无法枚举所有的 $j$ 取 $\min$。 发现 $f_{i,c}$ 要么是 $g_{a_i,c}$ 要么是 $g_{a_i,c}+1$，而颜色数很少，考虑状态压缩。把每个点压成二元组 $(a_i,\text{st})$，$\text{st}$ 为 $8$ 位二进制数，第 $c$ 位 $\text{st}(c)$ 表示 $f_{i,c}$ 为 $g_{a_i,c}$ 或者 $g_{a_i,c}+1$。 对于相同的二元组 $(x,\text{st})$，映射到不同的点。但是这些点到 $i$ 的距离都是相同的，为 $\min\limits_c\{f_{i,c}+1+g_{x,c}+\text{st}(c)\}$，可以一起统计进答案里面。复杂度降为 $O(8^22^8n)$，稍微剪枝就过了。