『模拟赛周总结』Day10-Day14
这五场模拟赛感觉打的不做评价，，，看排名来说不是那么悲观吧，，，
应yzh的要求，我先写一下Day13的T3是怎么改A的。
这个题首先一眼丁真线段树应该问题不大，毕竟都做过好多遍类似这样的线段树的题了。
题目中支持两个操作，第一个操作是翻转 \(0\) 和 \(1\) ，直接异或就行。第二个操作是查询标记是 \(1\) 的点的直径（等价于最长距离）。我们按照下标建线段树。
考虑怎么维护。这里有一个定理，就是一棵树上的两个点集，我们设为 \(\text{S}\) 和 \(\text{T}\) ，对于它们的直径端点集合（显然就两个点），我们设为 \(V(\text{S})\) \(V(\text{T})\) ，那么一定存在 $V(\text{S} \cup \text{T}) \subset (V(\text{S}) \cup V(\text{T})) $ 手模一下就知道了。
那么我们用每个线段树的节点维护区间的标记为 \(1\) 的个数（维护这个是为了好合并），直径的两个端点（如果只有一个被标记的点那么两个端点相同，如果没有被标记的点那么两个端点就都是 \(0\) ）。
合并的时候就是四选二，暴力枚举即可，单次合并时间复杂度 \(6\log n\) ，这 \(\log n\) 是求LCA来的。我们要留下来的就是直径最大的两个点。
另外求LCA的话用不了Tarjan（显然在线），千万别用倍增（后80pts全TLE），用树剖或ST表。
查询的话就简单了，你应该就明白了。