Codeforce 1399 E1. Weights Division (easy version) 解析(思維、優先佇列、樹狀DP)

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

題目
略，請直接看原題。

前言

沒有寫太久，還蠻開心的。

想法

如果能想到先去計算每條邊被計算過幾次，解法就不難得到了。
首先用樹狀DP去計算每個點，其子樹有多少個葉節點。那麼對於邊$u\to v$($v$是depth較深的點)，這個邊就會被計算$v$的子樹的葉節點次。
接下來只要用priority_queue去儲存${邊的長度,計算的次數}$這樣一個資料結構，且對於$u,v$兩個pair的大小關係是去比較邊權被除以二能夠減去的值，那麼只要每次取priority_queue頂端的邊，並將邊權除以二，直至邊權總和小於$S$即可。

程式碼:

const int _n=1e5+10;  
int t,n,S,u,v,w,ans,sum,cnt[_n];  
struct WE{int t,w;};  
struct W{int f,t,w;};  
struct P{int w,cnt;  
bool operator<(const P& rhs)const{return w*cnt-(w/2)*cnt<rhs.w*rhs.cnt-(rhs.w/2)*rhs.cnt;}};  
vector<WE> G[_n];  
vector<W> e;  
priority_queue<P> pq;  
void dfs(int v,int fa){  
  if(v!=1 and SZ(G[v])==1 and G[v][0].t==fa)cnt[v]=1;  
  for(WE& u:G[v])if(u.t!=fa)e.pb({v,u.t,u.w}),dfs(u.t,v),cnt[v]+=cnt[u.t];  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>t;while(t--){  
    cin>>n>>S;sum=0,ans=0;rep(i,0,n+1)G[i].clear();e.clear();  
    while(!pq.empty())pq.pop();  
    rep(i,0,n-1){cin>>u>>v>>w;G[u].pb({v,w}),G[v].pb({u,w});}  
    dfs(1,0);rep(i,0,n-1)pq.push({e[i].w,cnt[e[i].t]}),sum+=e[i].w*cnt[e[i].t];  
    while(sum>S){  
      assert(!pq.empty());  
      P now=pq.top();pq.pop();  
      sum-=now.w*now.cnt,sum+=(now.w/2)*now.cnt;  
      pq.push({now.w/2,now.cnt});  
      ans++;  
    }  
    cout<<ans<<'\n';  
    rep(i,0,n+1)cnt[i]=0;  
  }  
  return 0;  
}  

標頭、模板請點Submission看(注意，我其實有#define int long long)
Submission