你是第一个.jpg
考虑性质 B，我们会发现无论 Alice 怎么选，Bob 只有两种选择：\(1,2,...,n-1,n\) 或者 \(2,3,...,n,1\)。
考虑 \(S_i\) 和 \(T_i\) 的交集，如果交集为空，则我们可以忽略；如果交集恰好为 \(1\)，Alice 一定会去选这个交的，否则交集为 \(2\)。
设有 \(a\) 个交集为 \(1\) 的是交了 \(i\)，\(b\) 个交集为 \(1\) 的是交了 \(i+1\)，有 \(c\) 个交集为 \(2\)。
Alice 的任务其实是把 \(c\) 分配给 \(a,b\) 加上去，然后 Bob 选择其较小值。
我们此时容易 \(O(1)\) 计算出最优秀的结果。
考虑更一般的情况，我们希望沿用性质 \(B\)。首先，可以对 Bob 的选择集合做出一下的转化：
如果一个集合大小为 \(1\)，则我们确定它就是选这个数 \(x\)，则考虑 \(x\) 在其它集合中的出现，该集合只能选另外一个，递归做这个过程。
总之我们可以在 \(O(n)\) 的时间内消去这类只有一种选择的，现在每个位置都有两种选择。
把两个选择连边，则如果有一个环，我们可以暴力消去它，否则一定是若干个森林（由于无环）。
消环看上去是一个很困难的事情，但其实冷静思考并不是：一个连通块要么是树要么是基环树，不然就无解了。
基环树的话，环就直接套性质 B，然后环上的点等价于已经被占用了，因此剩下的部分也是方案唯一的，套用上面的化简过程。
树则比较麻烦。
最直接的想法是：我们对每条边，选深度比较大的那个作为真正的点，这样是合法的。
当然树根也是可以被占用的，这样相当于选一个点 \(u\)，它开始向上的边全部往上推，这样就把选中的点空了出来（显然我们恰好空一个点）。
这是 Bob 的方案，考虑 Alice。
先来考虑限制 C：如果 Alice 拿到的数和 Bob 没有交那就无所谓，否则如果这个点是比较深的点，则相当于当且仅当 Bob 选择 \(u\) 子树外的点会匹配上；如果是浅的点，等价于 Bob 选择 \(u\) 子树内的点才会匹配上。
所以我们执行子树加 / 子树外+，在 dfn 序上差分做这个事情，最后序列的最小值就是这棵树的答案。
场上就想到这里，但是没有写完。
一般情况的话，Alice 相当于是多了一种情形：可以自己选择子树 + 或者子树外 +，然后让最小值最大。
看上去套个二分先，但其实发现没有什么更好的性质了。
如果两个点不是祖孙关系，则不会同时执行子树加，这个没有同时执行子树外加优秀。
所以执行子树加的是一条根链。
初始的时候，把所有人都设置成子树外加的形态，然后在树上 dfs，把当前点的子树外加改成子树加，这是 Alice 的一种方案，此时的最小值是 Bob 对应的结果。
因此我们要支持：区间加减，全局求 min，上线段树维护就好了，复杂度 \(O((n+m)\log)\)。
标签：子树加,交集,Alice,选择,2023.4,Bob,我们 From： https://www.cnblogs.com/Cry-For-theMoon/p/17284696.html