标签：原图 P6185 联通 NOI 奇偶性 偶数 Online 考虑
P6185
- 首先考虑只有 \(t=2\) 的情况，我们发现假如把读入的所有边连成一张图，则在同一联通块的点可以通过不断传递做到一个 \(+1\) 一个 \(-1\) ，也就是说在这个联通块内的点的和是不会改变的，因此让这个联通块内 \(a_i=b_i\) 就等价于 \(\sum a_i = \sum b_i\)
- 然后考虑只有 \(t=1\) 的情况，先考虑如果是一条链的话会发生什么。对于这种题可以考虑选定两个点 \(u,v\) 看他们在什么情况下会改变成什么样子。
- 如果 \(dist(u,v)\) 为奇数，则可以让一个 \(+1\) 一个 \(-1\)
- 如果 \(dist(u,v)\) 为偶数，则可以让两个同时 \(+1\) 或 \(-1\)
- 把链放到图上就成了环，因此我们考虑对原题的环奇偶性分别判断：
- 若原图不存在奇环，说明原图是一个二分图，在同一集合的点两两距离都为偶数，不同集合的点两两距离为奇数，因此两两集合中点的和的差不会改变，直接判断即可
- 若原图存在奇环，则可以知道这个联通块内任意一个点都在一个奇环内，因此在图中可以让任意一个点 \(+1\) 或 \(-1\) ，但前提条件是操作次数必须是偶数，因此图中所有点的和的奇偶性不会改变，直接判断
- 最终复杂度 \(O(Tn)\)
标签：原图,
P6185,
联通,
NOI,
奇偶性,
偶数,
Online,
考虑
From： https://www.cnblogs.com/fox-konata/p/17793621.html