Codeforce 796 C. Bank Hacking 解析(思維)

今天我們來看看CF796C
題目連結

題目
略，請直接看原題。

前言

a

想法

首先稍微在腦中模擬一下大概整個流程是怎麼進行的，會發現以下幾件事:

1. 選取點$v$開始整個流程，之後是對以$v$為根的樹"Hack"，並且銀行防禦力增加只會加到子節點
2. 每個點最多被$+2$

那麼我們可以想到以下的結論:
首先維護$:$最大的$a[i]$($mx$)，次大的$a[i]$($smx$)，最大的$a[i]$的點的個數($cmx$)，次大的$a[i]$的點的個數($csmx$)

1. 如果$mx$只有$1$，那麼我們一定是從這個點開始，否則我們最少需要$mx+1$的力量(次大的點最多$+2$，也就是$smx+2$，其小於等於$mx+1$)。而如果這個點包含了所有的次大的點，那麼答案就是$mx$，否則就是$\max{smx+2,mx}$。
2. 如果$mx$有多個，那麼我們只需要遍歷所有點，看看有沒有點連接(含本身)了所有$a[i]$最大的點(就算點本身就是$mx$，由於有多個值為$mx$的點，我們最小還是需要$mx+1$的力量)，如果有，那麼答案就是$mx+1$，否則就是$mx+2$。(這個流程等於是遍歷所有的邊，所以複雜度是$O(2(n-1))$)

程式碼:

const int _n=3e5+10;  
int t,n,a[_n],cmx,csmx,mx=-1e9-1,smx=-1e9-1,cnt,uu,v;  
VI G[_n];  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n;rep(i,1,n+1)cin>>a[i];rep(i,1,n){cin>>uu>>v;G[uu].pb(v),G[v].pb(uu);}  
  rep(i,1,n+1)mx=max(mx,a[i]);rep(i,1,n+1)if(a[i]!=mx)smx=max(smx,a[i]);  
  rep(i,1,n+1)if(a[i]==mx)cmx++;rep(i,1,n+1)if(a[i]==smx)csmx++;  
  if(cmx==1){  
    rep(i,1,n+1)if(a[i]==mx)for(int u:G[i])if(a[u]==smx)cnt++;  
    if(cnt==csmx)cout<<mx<<'\n';  
    else cout<<max(mx,smx+2)<<'\n';  
  }else{  
    rep(i,1,n+1){  
      cnt=0;if(a[i]==mx)cnt++;  
      for(int u:G[i])if(a[u]==mx)cnt++;  
      if(cnt==cmx){cout<<mx+1<<'\n';return 0;}  
    }cout<<mx+2<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission