题解：CF2062D Balanced Tree

· · 题解

感觉 D 远大于 E1，卡了好久才做出来 qwq。

先考虑怎么根据区间给点赋初值更优，由于每次子树内加相当于是两个值不同的块合并的过程，合并是必定的，所以我们应当使每次加尽可能地少加一些不必要的点。因此每个叶子节点应当取最小值，记 a_v 为 v 这个点的值，对于一个点 u，定义 k=\max_{v\in son(u)} a_v，则 a_u 的取值为：

a_u=\begin{cases}\max(k,l_u),r_u\ge k \\ r_u,r_u<k\end{cases}

现在考虑将所有点的值变成一样的过程，应该是自底向上变成一样的。对于 u 为 v 的父亲，如果有 a_u\ge a_v，那么可以通过一直加 v 的子树变成相同的。否则就应当把 v 作为根，将 u 的子树一直加，直到 a_u=a_v。

现在考虑怎么维护这样的过程，加的过程相当于是将除了某一个子树整体加，最后统计单点的值，可以用 dfn 序加差分维护。

官方题解比我赛时写的更简单，因为最后每个点都是一样的值，所以只需要关注根节点的值，那么就变成当 a_v>a_u 的时候，将根节点加上 a_v-a_u 了。

代码很丑，但还是放着：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
const int maxn=2e5+20;
#define ll long long
ll t,n,val[maxn],b[maxn],cf[maxn],dfn[maxn],tot,siz[maxn],ans,f[maxn],rev[maxn];
vector<ll> e[maxn];
struct range{
    ll l,r;
}a[maxn];
void dfs(int u,int fa){
    ll flag=0,mx=0;
    dfn[u]=++tot,siz[u]=1,f[u]=fa,rev[tot]=u;
    for(int v:e[u]){
        if(v==fa) continue;
        flag=1,dfs(v,u);
        mx=max(mx,val[v]),siz[u]+=siz[v];
    }
    if(!flag) val[u]=a[u].l;
    else{
        if(mx<=a[u].r) val[u]=max(mx,a[u].l);
        else val[u]=a[u].r;
    }
}
inline void solve(){
    n=read(),tot=ans=0;
    for(int i=0;i<=n;i++) e[i].clear(),b[i]=cf[i]=0;
    int u,v;
    for(int i=1;i<=n;i++) a[i]={read(),read()};
    for(int i=1;i<n;i++) u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    dfs(1,0);
    for(int i=1;i<=n;i++) if(f[i]&&val[i]>val[f[i]]) b[i]=val[i]-val[f[i]];
    for(int i=1;i<=n;i++) cf[0]+=b[i],cf[dfn[i]]-=b[i],cf[dfn[i]+siz[i]]+=b[i];
    for(int i=1;i<=n;i++) cf[i]+=cf[i-1],ans=max(ans,cf[i]+val[rev[i]]);
    printf("%lld\n",ans);
}
int main(){
    t=read();
    while(t--) solve();
    return 0;
}