图论

线段树求直径可以求任意子树（包括连子树都不算的分散节点集合）的直径，适用范围广。 线段树的每个节点所对应的区间$[L, R]$，指代了$Dfn$在$[L, R]$内节点，其中线段树上每个节点存储了$diam$（当前区间直径）及$lp, rp$（当前直径对应的左右端点），每次$Merge$操作分为全左区间、全右区间和横跨两个区间作讨论，对于第三种情况，选择两侧原直径端点求$Dist$取最值即可，正确性显然，查询直接通过$Dfn$查询即可。 当然可能有一些区间内的点不连通，先当作它们连通即可。 对于删除某些子树，相当于把整棵树分为$n$部分，查询每个部分，全部$Merge$起来即可。 例题Snow的追寻 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 ...

说实话这题写树剖 $LCT$ 什么的真的思想又不难又好实现的样子，但是我还是选择自虐选择了动态点分治 那就两种做法都稍微提一下： 树链剖分 / $LCT$很容易可以发现一个换根操作只会对当前根在原树（根为 $1$ ）上的祖先一条链造成影响，也就是将它们的子树变成除当前链方向其它与之相连的点集，那么用树剖跳，用线段树维护一下原树上从上面来的和从下面来的，再将所有涉及的节点合并，并且删去算重复的和不该算的即可（虽然我没实现但是这个思路应该是对的 动态点分治首先有两篇博客：zzq、租酥雨 因为我们要算 $\sum\limits_{i = 1}^n s_i^2$ ，可以先想一下 $\sum\limits_{i = 1}^n s_i$ 怎么算，因为每个点的贡献只会被祖先计算到，那么易知 $\sum\limits_{i = 1}^n s_i = \sum\limits_{i = 1}^n value_i * (depth_i + 1)$ ，这个直接用动态点分治维护三个变量 $sumo_i, sumt_i, sumfa_i$ （sumo -> $p$ 子节点权值之和, $sumt$ -> ...

显然答案是总哈密顿回路数除以值得记录的竞赛图数 那么先求解总哈密顿回路数，考虑每个哈密顿回路会在几个值得记录的竞赛图中，则有$$Hamitons = (n - 1)!2^{C_n^2 - n}$$即总共有 $(n - 1)!$ 种哈密顿回路，然后剩下的边随便选 于是现在考虑值得记录的竞赛图数 首先如果一个竞赛图要有哈密顿回路，那么它至少要有一个包含所有节点的环，即该图是强连通的，并且显然非强连通竞赛图它一定不存在哈密顿回路，所以有结论 有且仅有强连通竞赛图存在哈密顿回路 那么问题转化为求解强连通竞赛图 发现正面难以求解，就考虑反面求解 设 $f_n$ 表示 $n$ 个节点的强连通竞赛图数，$g_n$ 表示 $n$ 个节点的竞赛图数（即 $2^{C_n^2}$），可得 $DP$ 方程$$f_n = g_n - \sum\limits_{j = 1}^{n - 1} f_jg_{n - j}\dbinom{n}{j}$$其中求解非强连通竞赛图部分是每次将拓扑序最小的强连通分量提取出来计数，那么剩下的点随意连接（注意，此时取的是拓扑序最小的强联通分量，故该强联通分量与其它连通分量的连边方 ...

这题真的是写到心态爆炸。。 一道边分治 + 虚树 前置知识边分治顾名思义，就是选择一条边，类似点分治对所有经过该边的路径进行处理，但与点分治不同的是，边分治可能会被菊花图卡到 $O (n^2)$，故此时需要重构树，将之变为度数不超过三的二叉树 树重构通过建立新的虚点进行重构，但要满足加入的虚点不影响最后答案计算 12345678910111213141516171819void rebuild (int root, int father) { int nf = 0; for (int i = Head[root]; i; i = Link[i].next) { int v = Link[i].to; LL w = Link[i].w; if (v == father) continue; if (! nf) { Insert (root, v, w), Insert (v, root, w); nf = root; } else { int k = ++ m; // 虚点 Insert (nf, k, 0), ...

计数问题也许可以转化为矩阵乘法形式 比如若该题没有不能在一条边上重复走的条件限制，那么直接将邻接矩阵转化为矩阵乘法即可 故 矩阵乘法计数对于计数问题，若可以将 $n$ 个点表示成 $n \times n$ 的矩阵，并且可以保证中途转移对象不会变化，即可用矩阵乘法计数 至于该题那么考虑该题，加入了不能重复在一条边上走的限制，那么最简单的思想就是拆点，并且让改点屏蔽掉当前方向，但是如果考虑边，一条无向边可以拆成两条有向边，那拆出来的就比点少很多了，故考虑点边转化 那么只要在起始点加一条超级源边，同样矩阵乘法即可统计答案 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110#include <io ...

前置「Hall定理」 二分图G中的两部分顶点组成的集合分别为X, Y(假设有|X|≤|Y||X|≤|Y|)。G中有一组无公共点的边，一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W的所有邻居， 霍尔定理即对于任意W，|W|≤|N(W) 题解由于最坏情况任选 $k$ 个是选一端连续的区间 $[l, r]$，根据Hall定理的 $|W| \le N(W)$ 可以得到$$\begin{aligned}sum[l, r] &\le (r - l + 1 + d) \cdot k \\sum[l, r] - (r - l +1) \cdot k &\le d \cdot k\end{aligned}$$那么就可以在线段树中将每个点的权值设为 $value - k$，然后维护最大子段和 $sumax$ 那么最后 $sumax \le d \cdot k ? TAK : NIE$ 即可 代码1234567891011121314151617181920212223242526272 ...

题意在一棵树上选出 $k$ 条可相交的链使得被覆盖的点数最多，求该最大值 题解说实话这个解法是真的厉害 显然题目可以看作选出 $k \times 2$ 个叶子节点，然后将它们互相连接最终覆盖的点的最大值 再考虑删去选中的 $k \times 2$ 个叶子节点后，向内一层的点最多只会有 $k \times 2$ 个点有贡献 同理继续内推 于是上述过程即由叶子节点开始拓扑，对于拓扑的每一层，令点 $i$ 拓扑深度为 $depth_i$，$total_i$ 表示拓扑深度为 $i$ 的点的个数，即，将每一个拓扑层重新看作叶子节点，再在当前拓扑层中选出至多 $k \times 2$ 个“叶子节点”，故$$\min (k \times 2, total_i)$$即为拓扑深度为 $i$ 的层的答案贡献 将它们累加起来即可 复杂度 $O (n)$ 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768 ...

题意求一个 $n$ 点 $m$ 边的 $DAG$ 的最长反链，在第二行输出构造的其中一种方案，在第三行输出在保证最长反链的前提下，每个点是否能够设置为反链中的点 题解反正证明也不会，就记录一下具体方法 最长反链：对 $DAG$ 点集 $V$，最长反链为一个集合 $S \subseteq V$，满足 $\forall u \in S, v \in S$，$u$ 不能到达 $v$，$v$ 也不能到达 $u$ 根据 $\text{Dilworth}$ 定理，一个 $DAG$ 的最长反链大小等于其最小可重链覆盖大小 对 $DAG$ 传递闭包后，最小可重链覆盖大小可转化为最小不可重链覆盖大小，即最小路径点覆盖 最小路径点覆盖：将 $DAG$ 用若干不相交的链覆盖，即每个点最多被经过一次，最小使用链的个数 那么最小可重链覆盖则是类似，不同之处仅在于每个点可被经过多次 最小路径点覆盖大小 $=$ $n$ $-$ 该 $DAG$ 拆点二分图的最大匹配大小 那么 $\text{Subtask1}$ 就做完了 把 $DAG$ 拆点后最小路径点覆盖就相当于是求该拆点二分图的最大独立集 接下来开始 ...

题意即为带修（临时）最短路 先随便提一条最短路出来，那么修改可分为四种情况： 该边在最短路上，且数值变小 该边在最短路上，且数值变大 该边在最短路外，且数值变小 该边在最短路外，且数值变大 那么对于情况 $1, 3, 4$，显然是十分容易处理的，那么问题就在情况 $2$ 设最短路经过点 $e_1, e_2, e_3, …$ 考虑到新的最短路必定与原最短路有相同的一段前缀与后缀（可以为空），设 $dis2_{i, j} (i < j)$ 表示不经过路径 $e_ie_j$ 的最短路，所以答案即为 $\min \{dis2 (e_ie_j) (i < j)\}$ 那么便两遍 $Dijstra$ 分别求出 $1, n$ 到每个点 $p$ 的最短路 $pre_p, suf_p$，并且对于最短路上的点 $e_i$，求出其在最短路上的前驱边 $from_{e_i}$ 与后继边 $nxt_{e_i}$，对于每个不在最短路上的点 $p$，求出点 $1$ 至 $p$ 中最后一个在原最短路上的点的后继边 $from_p$ 及点 $p$ 至 $n$ 中第一个在原最短路上的点的后继边 $nxt_ ...