Sürüşən Dəyərlər (Həll təhlili)

Həll

Biz yalnız dəyəri aşağıya doğru hərəkət etdirə bilərik: hər əməliyyat bir yarpağa aid olmayan $u$-dan a\ge 1 götürür və onu dəqiq bir uşağa əlavə edir, beləliklə daxili düyünlər azalır, lakin $1$-dən aşağı düşə bilməz, yarpaqlar isə heç vaxt azalmır. Beləliklə, son maksimum yarpaq dəyəri ən azı ilkin maksimum yarpaq dəyəri olacaq; daha da optimallaşdırılmış prosesdə artıq bu maksimuma çatmış bir yarpağa əlavə etməyə ehtiyac yoxdur, buna görə də son maksimumu

Sonra \max_L-\min_L-ni minimuma endirmək, əldə edilə bilən minimum yarpaq dəyəri $X$-ni maksimuma çatdırmaqla eynidir; cavab mx-X olacaq.

Çünki daxili düyünlər ən azı $1$ saxlamaq məcburiyyətindədir, hər bir yarpağa aid olmayan $u$ cəmi val[u]-1 vahidini öz nəsillərinə "bağışlaya" bilər. Bu, kodda yarpaqlara val[u]\leftarrow val[u]-1 əvəz etməyimizin dəqiq səbəbidir; bundan sonra, hər val[u] $u$-da qalan köçürülə bilən artıqdır (yarpaqlar tam dəyərlərini saxlayır). İndi hədəf minimum $X$-ni düzəldin və hər yarpağı ən azı $X$ edə biləcəyimizi soruşun. Bir yarpaq $\ell$ üçün onun $X$-ə nisbətən xalis artıq/defisit val[\ell]-X-dir; əgər mənfi olarsa, $\ell$-i ehtiva edən alt ağacın yuxarıdan X-val[\ell] vahidinə ehtiyacı var, əgər müsbət olarsa, o əlavə yuxarıya köçürülə bilməz, buna görə də ata üçün faydasızdır. Bu, $sum[u]$ massivi ilə aşağıdan yuxarıya DFS-yə gətirib çıxarır, $sum[u]$-nu val[u] (yarpaqlara $-1$-dən sonra) ilə başlamaqla. Bir uşağı $v$-dən qayıdarkən, artıq $v$-nin alt ağacında bütün yarpaqların $X$-ə çatması üçün xalis artıq $sum[v]$-ni hesablamışıq. Əgər $v$ bir yarpaqdırsa, əvvəlcə sum[v]\mathrel{-}=X edirik, onu val[v]-X-ə çeviririk. Sonra ata yalnız defisitləri ödəməyə məcburdur, buna görə də $sum[u]$-ya \min(0,sum[v]) əlavə edirik. Müsbət $sum[v]$ yuxarıya köçürülə bilmədiyi üçün nəzərə alınmır. Bütün uşaqları emal etdikdən sonra, $sum[u]$ $u$-nun alt ağacında bütün yarpaq tələblərini ödədikdən sonra qalan artıq miqdarı (mənfi qalan tələb) göstərir. Beləliklə, hədəf $X$ mümkündür, əgər DFS-dən sonra kökdə sum[1]\ge 0 varsa. Mümkünlük $X$-də monotonikdir, buna görə də $[0,mx]$ intervalında ən kiçik mid=mx-X-ni ikili axtarış edirik: X=mx-mid təyin edin, DFS yoxlamasını həyata keçirin, əgər sum[1]<0-da minimum çox yüksəkdirsə (artırın $mid$), əks halda $mid$-ni qeyd edin və daha kiçikini sınayın. Nəticədə $mid$ minimum mümkün \max_L-\min_L-dir. Hər yoxlama $\mathcal{O}(n)$-dir və biz \mathcal{O}(\log mx) yoxlamaları edirik, buna görə də ümumi \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;
}