一辈子都学不会的图论技巧

树的直径

树的直径具有许多优美的性质，我们将在以下几题探讨

最长性与对称性

树上一个点与其对应最长简单路径的另一端点一定是直径的端点，即直径的最长性，除此之外，直径上会存在中点，具有很好的对称性 #### [SDOI2011]消防

我们找出树的直径 \(\Gamma\) 则根据题意列出式子

\[ \min\lbrace \max_{p_{u,v}\subseteq\Gamma,d_{u,v}\ge s}\lbrace \max_{i\in p}\lbrace f_i\rbrace,d_{u,\Gamma},d_{v,\Gamma}\rbrace\rbrace \]

其中 \(f_i\) 表示不经过树的直径的最长长度，根据树的直径的最长性 \[ \max_{i\notin p,i\in\Gamma}\lbrace f_i\rbrace\le\min\lbrace d_{u,\Gamma},d_{v,\Gamma}\rbrace \]

所以中间部分可以修改上界，那么这道题直接用双指针维护即可

[AGC005C]Tree Restoring

最大值一定为直径，最小值一定为树的半径，根据直径奇偶性就可以确定最小值个数，再根据非半径路径的对称性判断即可

直径的合并

当合并两个联通块是，新的树的直径一定产生于原先两个树的直径的四个端点之中，当未指定合并方式时就可以通过控制连接点来构造我们想要的直径

[雅礼集训 2017 Day5]远行

动态维护树的直径的裸题，用 LCT 维护树上距离即可，不会 LCT 可以考虑启发式合并与倍增

多直径

这类问题通常会要求我们求出若干条边不相交或点不相交的链使得和最大

[APIO2010]巡逻

这道题很明显要找出两条不相交的链使得其和最大，由于边权都为 \(1\) 所以我们可以先求一边树的直径，再将直径上的边赋值为 \(-1\) 再求一遍树的直径就可以处理出合法的贡献

[51NOD]树的双直径

这道题依旧是两条直径，但边权为整数，所以考虑改进求树的直径的 DP，维护每个点子树内外的最长链，最长直链，次长直链换根 DP 即可，注意让乘积最大，且边权有负数，所以还要维护最小值和次小值

[八省联考2018]林克卡特树lct

思考题，不作要求，要选出 \(k\) 条直径，只能考虑直径的形态并用背包维护了，最后能发现凸性，用 WQS 二分即可

树的重心

树的重心有很多好看的特性，我们将在以下几题探讨

折半性与极少性

根据树的重心定义，树的重心是树上所有点在其被出去后使剩下联通块最大值最小的点，很明显这个最大值最小值小于整棵树大小的一半，点分治就是利用这一原理简化复杂度

并且，树的重心很少，最多不超过 \(2\) 个，无根树哈希以及无根无编号树的计数问题就利用了这个特性

[AGC018]Tree and Hamilton Path

根据贪心问题的套路，我们盲猜一波答案的上界，单独考虑每条边的贡献，我们让每条边利用充分，则贡献为

\[ \min(x,\ y)\times w \]

其中 \(x\) 和 \(y\) 是断掉这条边后树变成的两个联通块的大小

考虑什么时候答案可以达到上界，我们注意到当树存在双重心时，我们让两个重心连边断开后剩下的两个联通块互相配对即可达到上界，这启发我们找到合适的边或点断开，使剩下联通块配对即可，根据集合配对的结论，配对集合的最大值不超过总大小的一半即可完成配对，所以我们找到重心即可，注意这是路径，所以最后需要减去一条边的贡献

[CF1182D]Complete Mirror

可以发现若选择的点度数大于 \(2\) 必定是树的重心，否则以这个点为根时，各个子树大小都不平均，要么一定位于重心所在的长链上，画图很好证明，所以重心也暗含对称性

我们也可用同样具有对称性的直径或树哈希解决此问题，细节留给读者思考

带权重心

我们还可以定义重心为满足所有点到它距离和最小的点为树的重心，观察换根 DP 方程的转移，可以很明显发现这个定义与之前定义等价，当存在边权或点权，我们将重心扩展为带权重心

[ZJOI2015]幻想乡战略游戏

思考题~~由于没有找到在联赛范围的题~~，动态维护带权重心，利用线段树在点分树上二分即可

重心的移动

当两个联通块合并时，树的重心一定位于原来两个联通块重心的连线上，结合带权重心的定义理解，若可以往外移动，则在未合并前就已经移动了

树的遍历序

树的遍历序可以转化树上问题为序列上的偏序问题

DFS 序

DFS 序最直接的利用应该就是重链剖分中把树转化为序列问题，和虚树中的利用，其中对应的实质是 DFS 序使子树连续，以及它的子序列所对应的联通块极大的性质

[CF1225F]Tree Factory

很明显最后要求的就是树的一个 DFS 序，那么 dfn 中的第 \(i\) 个点贡献为 \(d_{dfn_{i-1}}-d_{fa_{dfn_i}}\) 显然最后走长链即可

BFS 序

BFS 序不经常使用，最基础的一个性质是相邻两个节点要么为兄弟要么为父亲，且位于深度之差小于 \(1\)，可以在某些题优化做法

[CF893F]Subtree Minimum Query

以 BFS 序为时间做可持久化线段树，维护 DFS 序信息，支持询问区间最值即可

树上统计信息

对具有区间可减性的树上信息可以通过前缀和和差分高效维护，也可以通过考虑每条边或点的贡献高效统计

差分

我们类比序列的差分，可以看出树也可以差分性质，树链(u, v) 的点权加即在 u 和 v添加贡献，fa[lca(u, v)] 和 lca(u, v) 减去贡献

[LGP1600]天天爱跑步

考虑每个点会被哪些路径产生贡献，显然对于路径 (u, v) 上行部分满足 \(d_u=d_i+w_i\) 下行满足 \(d_{u,v}-d_v=w_i-d_i\) 会产生贡献，树上差分用桶统计即可

前缀和

类比序列的前缀和，我们也可以维护每个点到根的信息和

[AGC014]Unplanned Queries

很明显我们只关注奇偶性，对每条链的统计实际上通过反向考虑前缀和等价于链的每个端点到根的奇偶性，在这个意义下树的形态就不重要了，所以随便找一种判断即可

贡献单独考虑

[HAOI2015]树上染色

题干中要求统计树上点对两两之间的距离所以很套路的就可以考虑每条边的贡献为两边黑点和白点数量的乘积，直接树上背包就好了

[HAOI2018]苹果树

同样是是求距离之和，所以我们只需要把大小作为状态转移即可，和这道题类似的计数题还有 [CF855G]Harry Vs Voldemort ~~需要大力分类讨论~~ 和 [WC2019]数树 ~~需要大力推式子~~

[AGC005]Many Easy Problems

求大小之和，很自然地想到每个点会被多少个联通块算到，不妨设联通块大小为 \(k\)，删去一个点后剩下地联通块集合为 \(S\) 则贡献为

\[ \binom{n}{k}-\sum_{s\in S}\binom{s}{k} \]

直接统计复杂度为 \(O(n^2)\) 所以还要搞一下答案生成函数，用 NTT 即可解决

图论建模

一些人类智慧题可以通过建立图论模型解决

欧拉路

感觉自己就没做出来过欧拉路的题

当我们发现以每个积木作为点建图很难搞，考虑把积木当作边，对于每个积木而言左边若 \(c=0\) 则当作编号为 \(a\) 的点，否则为 \(-c\)，右边而言若 \(d=0\) 则当作编号为 \(-b\) 的点，否则为 \(d\)，积木本身作为连接两点的边，现在题目等价于求若干条不边相交的路径覆盖图的问题，且对于每条路径而言必须从编号为正的路径开始，编号为负的路径结束，所以编号为正的路径的出度必须大于等于入度，标号为负的路径入度必须大于出度，且对于每一个联通块而言入度和出度不能相等

二分图

这里重点强调的是二分的匹配问题

[AGC018]Two Trees

首先一个很明显的事实是，对于两棵树而言，若两个标号相同的点，他们子节点个数奇偶性必然相同，否则一定无解，接着我们考虑构造方案，首先我们把子节点个数为偶数的点的值赋值为零，其他节点赋值为 \(1\) 或 \(-1\)，那么每颗子树一定有 \(2k+1\) 个奇数点，我们把这些节点自底向上两两配对，不能配的上传到父亲，配对关系可以建图，这样每个点的度数为 \(2\) 并且一条是在树 A 产生的边，另一条是在树 B 产生的边，一个点只有两者交替才能回到自己，所以图为二分图，可以产生匹配方案

有向无环图

一般在字典序问题或排列问题起到作用

[AGC010]Rearranging

互质的数不会交换，先后顺序不变，所以将互质的数之间连边，那么先手操作为给边定向，后手操作为求 DAG 的最大字典序，两遍贪心即可

[AGC001]Wide Swap

首先题干中的条件有点复杂，我们不妨把排列的下标和值互换，这样最后求出字典序最小与原问题等价，发现这样题干中的交换条件就变为交换差值超过 \(k\) 相邻两个数，那么差值不超过 \(k\) 的一定不会交换，和上一题一样又转变为 DAG 字典序最小拓扑序问题，但这是 \(O(n^2)\) 的建边，所以考虑优化，最终发现只需要向里当前点最近的连边即可

最小生成树

最小生成树我自己也不太会啊 QAQ