有意思的题，做这题的时候也发现了不少有趣的东西虽然不会做。
考场上没有看出来建图。事实上本题复杂的性质基本决定它需要一步图论转化，而互不相同也是一个经典限制。可以得到如下建图转化：对于集合 \(T_i\) 的两个数，在它们之间建立无向边，用定向表示选择，则我们需要给边定向使得每个点的入度不超过 \(1\)，而只有当形态是树或者基环树的时候才会有定向方案。
基环树是简单的，因为方案只有两种。只需要考虑树的做法。问题是，Alice 需要决定 \(S_i=T_i\) 的时候贡献放在哪边，使得以所有点为根的外向树的权值最小值最大。观察一条边的贡献，它一定是一个连通块。观察两条边的贡献，发现如果它们贡献到的连通块没有交，则将它们反向可以得到更优解。所以最终所有边贡献到的连通块一定是有交的。我们枚举交中的一个点，就可以确定所有边的定向方案。这是一个平方做法。
考虑利用换根 DP 优化到线性，我们需要维护出每个点在交内时全局最小值的大小，而这是容易维护的。
本题值得借鉴的是建图的思想，和观察最优性时的技巧：从 \(S_i=T_i\) 只有一条边出发，扩展到两条边，再推广到更一般的结论。
特殊性质 C
来写特殊性质是因为我搞出了一堆互不相干的做法，下面可能比较意识流。
性质 C 存在一个费用流做法。互不相同等价于每个值只出现一次，把值建立点，位置也建立点即可。
平方
有一个和上面的平方做法不同的平方做法。
考虑利用 DP 构造每条边的定向方案，容易发现一个性质：子树外的边的定向方案对子树内所有点的贡献是相等的，所以只要维护出这个贡献即可。考虑 \(u\) 并上一个子树 \(v\) 会对 \(u\) 子树内带来多少贡献，显然它就是 Bob 把 \(v\) 的所有边都向下定向而产生的贡献。设 \(f_{u,x}\) 表示 \(u\) 子树内贡献为 \(x\) 的每个点为根的答案最小值的最大值，合并后的值就是 \(\min(f_{u,x}+y,f_{v,y}+x)\)，每次转移的时候枚举边的定向并加入贡献，类似背包，复杂度为平方。
特殊性质 D
有一个能做 D 但是不能做正解的做法。没写过不保证是对的。
直接观察性质看似陷入了瓶颈，考虑枚举一些值来加强限制。此题要求最小值的最大值，不妨枚举最小值的位置 \(rt\)，则问题变为：
- 保证它是最小值。
- 最大化它的答案。
对于前者，观察可以发现相邻两个点的差就是这条边对它们两个点的贡献差。假设它对 \(rt\) 的贡献为 \(1\)，则造成的差就是 \(-1\)，否则若贡献为 \(0\)，则造成的差为 \(1\)。所以我们相当于要将每条边标上 \(0/1\)，使得：
- 以 \(rt\) 为根，前缀 \(0\) 的个数多余前缀 \(1\) 的个数。
- \(1\) 的个数尽可能多。
做一些简单的调整可以发现，若 \(1\) 是 \(0\) 的祖先，交换 \(0,1\) 是不劣的。故对于树上一条链，必定是 \(0\) 为一个前缀，\(1\) 为一个后缀。
简单分析就可以得到一条边对一个点有贡献的条件，利用数据结构可以做到 polylog。不过由于在没有性质的时候条件过于复杂，不能拓展到正解。
标签：省选,枚举,贡献,最小值,填数,loj3959,做法,定向,性质 From： https://www.cnblogs.com/yllcm/p/17341763.html