Balancing a Tree (USACO Gold 2022 US Open)

Balancing a Tree (USACO Gold 2022 US Open)

这是一个比较考思维能力的数学不等式题。

  1. 从题目测试点描述，可以猜到一长串的形状是重要的，把这个拿出来仔细看。可以得到以下结论，对于一串节点，最小化的平衡度为：
ans=max⁡(min⁡iri−max⁡ili,0)\text{ans} = \max(\min_{i} r_i - \max_{i} l_i, 0)

这个意思就是说，一串节点上面，最优情况下最右侧点的取值受lil_i限制（最小值），而最左侧点的取值受rir_i限制（最大值）。

  1. 再看整个树，这时候每一个节点ii对最后范围的影响，除了从ii开始到根这个一串节点如上面的公式计算之外，整棵树还存在最右侧节点和最左侧节点，这时候还会导致不平衡度至少为这个范围的一半。
ans=max⁡(max⁡i(min⁡j=i,或者i的祖先rj−max⁡jlj),(min⁡li−max⁡ri)/2,0)\text{ans} = \max( \max_i(\min_{{j=i, \text{或者}i\text{的祖先}}} r_j - \max_{j} l_j), (\min l_i - \max r_i)/2, 0)
  1. B=1B=1的时候要输出一个方案，这个就是所有值都向(min⁡li−max⁡ri)/2(\min l_i - \max r_i)/2这个中点靠拢就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;  // 2e5
int p[200005], l[200005], r[200005], L[200005], R[200005], L2, R2;
int T,B;
int ans;
const int INF = 1e9;
 
int main() {
    scanf("%d %d", &T, &B);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i < n; i++) {
            scanf("%d", &p[i]);
            p[i]--;
        }
        ans = 0;
        L2 = INF, R2 = -INF;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &l[i], &r[i]);
            L[i] = r[i]; R[i] = l[i];
            if (i) {
                L[i] = min(L[p[i]], L[i]);
                R[i] = max(R[p[i]], R[i]);
            }
            L2 = min(L2, r[i]);
            R2 = max(R2, l[i]);
            ans = max(ans, R[i]-L[i]);
        }
        ans = max(ans, (R2-L2+1)/2);
        int mid = (L2+R2)/2;
        printf("%d\n", ans);
        if (B)
            for (int i = 0; i < n; i++)
                printf("%s%d", i ? " " : "", r[i] < mid ? r[i] : l[i] > mid ? l[i] : mid);
        printf("\n");
    }
    return 0;
}