CF869D The Overdosing Ubiquity 解题报告

CF869D The Overdosing Ubiquity 解题报告：

题意

给定一个 \(n\) 个结点的完全二叉树，\(k\) 号点的父亲为 \(\lfloor\frac{k}{2}\rfloor\)，新加 \(m\) 条边，求本质不同简单路径数量。

\(1\leqslant n\leqslant 10^9,0\leqslant m\leqslant 4\)。

分析

给一个常数大，码量大但好想的做法。

首先不经过新加边的路径数量就是 \(O(n^2)\)，然后考虑强制经过新加边的方案数。

由于 \(m\) 很小，我们可以枚举选哪些边，枚举走边的顺序，枚举边的方向（也就是无向边变成有向边），然后考虑按照顺序依次经过钦定的边的路径数量。

我们令 \((x_i,y_i)\) 为选择的第 \(i\) 条新加边（一共 \(k\) 条），取出两条路径 \(A\) 和 \(B\)。

\(A\)：从 \(y_1\) 沿着树上的边走到 \(x_2\)，然后走 \((x_2,y_2)\)，再从 \(y_2\) 沿着树上的边走到 \(x_3\)……
\(B\)： \(x_1\) 沿着树上的边走到 \(y_k\) 的路径。

若 \(A\) 与 \(B\) 有交，那么可以发现经过这些钦定边的路径的起点一定是 \(x\) 不经过 \(A\) 内点沿着树上的边能到达的点，同理终点一定是 \(y\) 不经过 \(B\) 内点沿着树上的边能到达的点。

这个东西可以直接在树上搜一遍得到，也可以发现这个连通块一定是一个子树去掉若干子树的结果，大子树和去掉的子树都可以枚举 \(A\) 上的点计算出来，具体可以看代码。（\(\text{dfs}\) 部分）

若 \(A\) 与 \(B\) 没有交，那么可以发现我们几乎可以在 \(A\) 与 \(B\) 到达的点中任选两个点作为起点和终点，但是这两个点 \(s,t\) 要满足 \((x_1,s)\) 与 \((y_k,t)\) 无交
，我们枚举 \(B\) 上所有点，令枚举的点为 \(s\) 的祖先，那么 \(t\) 一定在 \(B\) 更后面的点的子树中，于是前缀和一下就做完了。

然后你就写出了大分讨代码，接下来就只需要足够的耐心调试了！

时间复杂度 \(O((m\log n)^3m!4^m)\)，非常松，随便过。

代码

#include
#include
#include
#include