CF2062D Balanced Tree 题解

_fairytale_ · 2025-01-27 20:48:00 · 题解

-87，哈哈。

我们随便定一个根，然后把操作改写成子树 +1，或者全局 +1，子树 -1。

有一个性质是，在每个点的 a 确定的时候，我们自底向上考虑每棵子树，对于点 u，如果我们忽略掉全局加，那么它子树中的值都会变成 a_u。

回到原题，一个贪心的想法是直接令 a_i=l_i。我们发现在叶子上这么做完全没有问题，问题出现在一个点小于它子树的时候，这个时候会带来一个全局加，但是全局加不优于子树加，于是记录一下儿子的 \max，取 a_i 为尽可能接近儿子 \max 的值即可。

void Solve_(){
    int n;
    cin>>n;
    vector<int>l(n+1),r(n+1);
    rep(i,1,n)cin>>l[i]>>r[i];
    vector<vector<int>>g(n+1);
    for(int i=2,u,v;i<=n;++i){
        cin>>u>>v;
        g[u].ep(v),g[v].ep(u);
    } 
    vector<ll>f(n+1);
    vector<int>a(n+1);
    auto dfs=[&](auto &self,int u,int fa)->void{
        for(int v:g[u])if(v!=fa){
            self(self,v,u);
            ckmax(a[u],a[v]);
            f[u]+=f[v];
        }
        if(a[u]<l[u])a[u]=l[u];
        else if(a[u]>r[u])a[u]=r[u];
        for(int v:g[u])if(v!=fa)if(a[u]<a[v])f[u]+=a[v]-a[u];
    };
    dfs(dfs,1,0);
    cout<<a[1]+f[1]<<'\n';
}