LOJ6119 「2017 山东二轮集训 Day7」国王
LOJ 分析 考虑一个区间怎样才是满足条件的。 设 $A_{l,r}$ 为端点都在 $[l,r]$ 内的 exciting 的路径数，$B_{l,r}$ 为端点都不在 $[l,r]$ 内的 exciting 的路径数。则 $[l,r]$ 满足条件即 $A>B$。 现在我们要比大小，根据文化课那一套理论可以想到作差。设 $C_{l,r}$ 为一个端点在 $[l,r]$ 内、一个端点不在 ...
LOJ 分析 考虑一个区间怎样才是满足条件的。 设 $A_{l,r}$ 为端点都在 $[l,r]$ 内的 exciting 的路径数，$B_{l,r}$ 为端点都不在 $[l,r]$ 内的 exciting 的路径数。则 $[l,r]$ 满足条件即 $A>B$。 现在我们要比大小，根据文化课那一套理论可以想到作差。设 $C_{l,r}$ 为一个端点在 $[l,r]$ 内、一个端点不在 ...
CodeForces 分析 考虑点分治，那么需要考虑如何拼合两条路径。 设根到 $x$ 的路径上的数是 $d_1$，根到 $y$ 的路径上的数是 $d_2$，根到 $y$ 的距离为 $dep$。那么若 $x\to y$ 这条路径合法，则需要满足： 这样子两条路径就独立了，分别存下来后枚举 $y$ 统计即可。 代码 //It is made by M_sea #include <alg...