从 2024.10.14 考图论起。
2024.10.14 考图论
T1
转前缀和，跑差分约束或者贪心，贪心用[树状数组、并查集]（？）实现。
注意前缀和的额外限制（差分约束）、贪心实现的正确性。
T2
相当于连无向边，两点连通就能得到差。
注意到没必要连接两个已经连通的点，于是会形成一棵树。
带权并查集 或者 用并查集建树，离线下来在树上跑，再用并查集做。
T3
类似差分约束，但是注意到只有小于的关系，于是拓扑排序找 DAG 上的最长链即可。
似乎要注意 边权 和 起点的值。
建图：
- 线段树优化建图。似乎线段树动态开点写起来较方便。
- 也可用 线段树 + 并查集，在跑拓扑排序的时候动态维护。
T4
要使平均数是 n，发现直接做不好做。注意到平均数的特殊性，直接推式子转化。
（可以用算平均数的式子推出，也可以直接理解出）
标签：2024.10,23,线段,查集,差分,考试,贪心 From： https://www.cnblogs.com/huangkxQwQ/p/18494297