Sliding Values (Editorial)

Solution

We can only move value downward: every operation takes some a\ge 1 from a non–leaf $u$ and adds it to exactly one child, so internal nodes decrease but can never drop below $1$, while leaves never decrease. Hence the final maximum leaf value is at least the initial maximum leaf value; moreover in an optimal process we never need to add to a leaf that already attains this maximum, so we may fix the final maximum to be

Then minimizing \max_L-\min_L becomes the same as maximizing the achievable minimum leaf value $X$; the answer will be mx-X.

Because internal nodes must keep at least $1$, each non–leaf $u$ can "donate" at most val[u]-1 units in total to its descendants. This is exactly why we replace val[u]\leftarrow val[u]-1 for non–leaves in the code; after that, every val[u] is the remaining transferable surplus in $u$ (leaves keep their full value). Now fix a target minimum $X$ and ask if we can make every leaf at least $X$. For a leaf $\ell$ its net surplus/deficit relative to $X$ is val[\ell]-X; if it is negative the subtree containing $\ell$ needs X-val[\ell] units from above, if positive that extra cannot be moved upward so it is useless to ancestors. This leads to a bottom-up DFS with an array $sum[u]$ initialized as sum[u]=val[u] (after the $-1$ on non-leaves). When returning from a child $v$ we already computed its net surplus $sum[v]$ for making all leaves in $v$'s subtree reach $X$. If $v$ is a leaf we first do sum[v]\mathrel{-}=X, turning it into val[v]-X. Then the parent can only be forced to pay deficits, so we add \min(0,sum[v]) to $sum[u]$. Positive $sum[v]$ is ignored since it cannot travel upward. After processing all children, $sum[u]$ represents how much surplus remains in $u$'s subtree after satisfying all leaf requirements there (negative means remaining demand). Thus the target $X$ is feasible iff after DFS at the root we have sum[1]\ge 0. Feasibility is monotone in $X$, so we binary search the smallest range mid=mx-X in $[0,mx]$: set X=mx-mid, run the DFS check, and if sum[1]<0 the minimum is too high (increase $mid$), otherwise record $mid$ and try smaller. The resulting $mid$ is the minimum possible \max_L-\min_L. Each check is $\mathcal{O}(n)$ and we do \mathcal{O}(\log mx) checks, so total \mathcal{O}(n\log mx).

#include <bits/stdc++.h>
#define int long long
#define ld long double
#define nl "\n"
#define ull unsigned long long
#define rv return void
#define str string
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define vec vector
#define fixed(n) fixed << setprecision(n)
#define Moageza ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;
vec<int>sum,v,vis;
vec<vec<int>>adj;
void dfs(int node,int par,int val){
    for(auto it:adj[node]){
        if(it==par)continue;
        dfs(it,node,val);
        if(vis[it]==1){
            sum[it]-=val;
        }
        sum[node]+=min(0LL,sum[it]);
    }
}
void solve()
{
   int n;cin>>n;
  v.assign(n+1,0),vis.assign(n+1,0),adj.assign(n+1,{});;
   for(int i=1;i<=n;i++)cin>>v[i];
   for(int i=0;i<n-1;i++){
    int a,b;cin>>a>>b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    vis[a]++,vis[b]++;
   }
   int mx=0;
   vec<int>ans;
   for(int i=1;i<=n;i++){
    if(vis[i]==1){
        mx=max(mx,v[i]);
        ans.push_back(i);
    }
    else v[i]--;
   }
   int l=0,r=mx,res=0;
   while(l<=r){
    int mid=(l+r)/2;
   sum.assign(n+1,0);
   for(int i=1;i<=n;i++)sum[i]=v[i];
   dfs(1,0,mx-mid);
    // cout<<sum[1]<<" ";
    if(sum[1]<0)l=mid+1;
    else {
        res=mid;
        r=mid-1;
        // cout<<mid<<" ";
    }
   }
   cout<<res;
}
signed main()
{
    Moageza
     #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    #endif
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
        cout << nl;
    }
    return 0;
}