Зсув значень (Розбір)

Розв'язок

Ми можемо лише переміщати значення вниз: кожна операція забирає деяке a\ge 1 з нелистового $u$ і додає його точно одному дитині, тому внутрішні вузли зменшуються, але ніколи не можуть опуститися нижче $1$, тоді як листи ніколи не зменшуються. Отже, фінальне максимальне значення листа принаймні дорівнює початковому максимальному значенню листа; більше того, в оптимальному процесі нам ніколи не потрібно додавати до листа, який вже досяг цього максимуму, тому ми можемо зафіксувати фінальне максимальне значення як

Тоді мінімізація \max_L-\min_L стає такою ж, як максимізація досяжного мінімального значення листа $X$; відповідь буде mx-X.

Оскільки внутрішні вузли повинні зберігати принаймні $1$, кожен нелист $u$ може "пожертвувати" максимум val[u]-1 одиниць загалом своїм нащадкам. Саме тому ми замінюємо val[u]\leftarrow val[u]-1 для нелистів у коді; після цього кожне val[u] є залишковим переносимим надлишком у $u$ (листи зберігають своє повне значення). Тепер зафіксуйте цільове мінімальне $X$ і запитайте, чи можемо ми зробити так, щоб кожен лист був принаймні $X$. Для листа $\ell$ його чистий надлишок/дефіцит відносно $X$ дорівнює val[\ell]-X; якщо він негативний, піддерево, що містить $\ell$, потребує X-val[\ell] одиниць з верхніх вузлів, якщо позитивний, то цей надлишок не може бути переміщений вгору, тому він марний для предків. Це призводить до обходу DFS знизу вгору з масивом $sum[u]$, ініціалізованим як sum[u]=val[u] (після $-1$ для нелистів). Коли ми повертаємося з дитини $v$, ми вже обчислили її чистий надлишок $sum[v]$ для досягнення всіх листів у піддереві $v$. Якщо $v$ є листом, ми спочатку робимо sum[v]\mathrel{-}=X, перетворюючи його на val[v]-X. Тоді батько може бути змушений платити лише дефіцити, тому ми додаємо \min(0,sum[v]) до $sum[u]$. Позитивний $sum[v]$ ігнорується, оскільки він не може подорожувати вгору. Після обробки всіх дітей, $sum[u]$ представляє, скільки надлишку залишається в піддереві $u$ після задоволення всіх вимог листів там (негативне означає залишковий попит). Таким чином, цільове $X$ є здійсненним, якщо після DFS на корені ми маємо sum[1]\ge 0. Здійсненність є монотонною в $X$, тому ми бінарно шукаємо найменший діапазон mid=mx-X в $[0,mx]$: встановлюємо X=mx-mid, запускаємо перевірку DFS, і якщо sum[1]<0, мінімум занадто високий (збільшуємо $mid$), в іншому випадку записуємо $mid$ і намагаємося менше. Отриманий $mid$ є мінімально можливим \max_L-\min_L. Кожна перевірка є $\mathcal{O}(n)$ і ми робимо \mathcal{O}(\log mx) перевірок, тому загалом \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;
}