P4149 [IOI2011]Race 题解

题面

感觉和板子差不多，但是仔细思考一下就会发现，用两个指针扫的时候很难维护 “不选某个子树”的最小值。这时候需要设计一个排序和贪心方案，使得能够使用模板那种双指针方式解决问题。

首先是几个定义：在对于某个根 \(rt\) 更新答案的时候，设 \(a[]\) 表示子树的所有点，\(b[]\) 表示每个点属于 \(rt\) 的哪一个儿子的子树，\(d[]\) 表示每个点到 \(rt\) 的距离，\(len[]\) 表示每个点到 \(rt\) 经过的边数。

考虑把 \(a\) 按照第一关键字 \(d\) 从小到大，第二关键字 \(len\) 从小到大。那么首先可以确定一件事情：如果匹配同一个点，靠前的一定比靠后的更优。更具体地，如果两个点 \(b,d\) 都相等，那么位置靠后的无论什么情况下都更劣，因为它能匹配到的点，靠前的那个点也能匹配到。根据这个性质，可以直接对整个数组双指针，当 \(d_{a_l}=d_{a_r}\) 时，若 \(d_{a_{r-1}}=d_{a_r}\) 则 --r，否则 ++l。这样的话，如果在 \(l\) 附近和 \(r\) 附近都有 \(d\) 相等的段，看似会使得有些答案跳过去无法计算，但是可以证明这些被跳过去的一定不会更优。具体证明如下：

设 \(l\) 目前位于 \(l_1\)，颜色为 \(a\)；\(r\) 目前位于 \(r_1\)，颜色为 \(a\)；\(l+1\) 位置为 \(l_2\)，颜色为 \(b\)；\(r-1\) 位置为 \(r_2\)。这些位置的 \(d\) 均相等。

因为 \(b_{l_1}=b_{r_1}\)，并且 \(d\) 均相等，所以会导致 --r，也就是说，\(l_2\) 无法和 \(r_1\) 匹配。这时候可以对 \(r_2\) 的颜色分类讨论：

1. 若 \(r_2\) 颜色为 \(b\)，则 \(l_1\) 和 \(r_2\) 可以匹配，因为 \(l_1\) 优于 \(l_2\) 且 \(r_2\) 优于 \(r_1\)，所以无法匹配的 \(l_2\) 和 \(r_1\) 一定不会更优；
2. 若 \(r_2\) 颜色不为 \(b\)，则 \(l_2\) 和 \(r_2\) 可以匹配，同理，这样也一定比 \(l_2\) 和 \(r_1\) 更优。

综上所述，这样做所出现的无法匹配的情况都不可能成为最优情况。

这样就可以用这个方法解决这道题了，复杂度因为有排序，所以是 \(O(n\log^2 n)\)，常数较小，可以通过此题。

#include
#include
#include
using namespace std;
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return ak) --r;
		else if(d[a[l]]+d[a[r]]