图论杂题记录

图论太差了，微补了一点，全都是 2100\sim 2400 的水题。

有没有一种可能，在之前我都不会 dfs 树。

建出 dfs 树以后，除了树边只有横跨边和返祖边，且每个环一定有树边和返祖边，将树边染 1 ，返祖边染 2 ，其他随意即可。

考虑从 1\sim n 一个个点插入图内，维护并查集。

插入 u 时，先令它是独立的一个集合，然后考虑它与之前集合的连边，如果它与之前某个集合里所有点都没有边的话，那么将它和这个集合合并即可。对每个集合暴力标记一下 siz 。

考虑这样做为什么复杂度是对的，因为一共只有 2\times 10^5 个关系，那么集合数量不会多于 \sqrt m 。

恶心的是区间连边，考虑利用线段树建出点，那么每个区间被拆成了 \log n 个点，然后直接连边跑最短路。

两种操作建出两个线段树即可。

先用 Tarjan 在原图上跑环然后缩点，那么对于每个环，每个点的 R_i+=siz 。

现在得到了一棵树，每个点带点权，R_i 的定义变成能到达的点的点权和。

因为只有 n-1 条边，就算一条边对应一个点，那么也一定会有一个点无法到达其它点。

考虑以点权最大的点为树根，建出一棵内向树即可，这样答案就是这个点的点权。

按照边权分类，从小到大排序。

对于相同的边权，无论怎么连，任意两点的连通性是一样的。

每次一个边权，考虑对于每个询问分别考虑，将这个询问里所有该边权的边连上，看看是否有环即可。

然后跑完再把这个边权的所有边都连上即可，原理在上两行。

显然把最大值和最小值分开计算，会最大值就会最小值。

考虑点分治，每次维护 mx_i 表示 i 到 root 路径上的最大值。

考虑怎么计算，假设现在到 u ，首先考虑对于 mx_i\le mx_u 的，统计 i 的个数 cnt 然后对答案的贡献就是 cnt\times mx_u 。

对于 mx_i > mx_u 的，统计 mx_i 的和即可。

上述两种情况分别开两个树状数组即可。

这个做法好像是 O(n\log^2 n) 的，可能比较卡常。

考虑一个 log 的做法，先 dfs 一遍把点权弄成边权，然后对于最大值，从小到大加入边，那么这条边的贡献就是 siz_u\times siz_v 。

复杂度 O(n\log n) ，而且只是排序的 \log 。