結果
問題 |
No.1488 Max Score of the Tree
|
ユーザー |
|
提出日時 | 2023-07-21 21:31:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 2,596 bytes |
コンパイル時間 | 1,147 ms |
コンパイル使用メモリ | 100,080 KB |
最終ジャッジ日時 | 2025-02-15 16:24:02 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include<iostream> #include<set> #include<map> #include<vector> #include<queue> #include<algorithm> #include<tuple> using namespace std; typedef pair<int,int> P; typedef long long ll; const ll INF=1LL<<60; struct edge{ int from; int to; ll cost; int id; edge(int from_,int to_,ll cost_,int id_):from(from_),to(to_),cost(cost_),id(id_){}; }; int main(){ int N,K; cin>>N>>K; vector<vector<edge>> G(N); vector<edge> edges; vector<int> A(N-1),B(N-1),C(N-1); for(int i=0;i<N-1;i++){ cin>>A[i]>>B[i]>>C[i]; A[i]--; B[i]--; G[A[i]].emplace_back(A[i],B[i],C[i],i); G[B[i]].emplace_back(B[i],A[i],C[i],i); } vector<int> cnt(N);//cnt[i]=辺iをとおっていくことができる葉の数 vector<int> depth(N);//0からどれだけ離れているか //部分木の葉の数を数える auto dfs=[&](auto f,int now,int pre)->int{ bool flag=true; int res=0; for(edge e:G[now]){ if(e.to==pre) continue; flag=false; int tmp=f(f,e.to,now); //e.toの部分木にある葉の数 cnt[e.id]+=tmp; res+=tmp; } if(flag){ //now自身が葉 return 1; } return res; }; dfs(dfs,0,-1); vector<pair<ll,ll>> load; for(int i=0;i<N-1;i++){ //i番目の辺 load.emplace_back(C[i],C[i]*cnt[i]); //i番目の辺の重さとコスト edges.emplace_back(A[i],B[i],C[i],i); } /* for(int i=0;i<N;i++){ cout<<"depth["<<i<<"]="<<depth[i]<<endl; } */ vector<vector<ll>> dp(N,vector<ll>(K+1,-INF)); dp[0][0]=0; for(int i=0;i<N-1;i++){ for(int j=0;j<=K;j++){ if(dp[i][j]==-INF) continue; dp[i+1][j]=max(dp[i+1][j],dp[i][j]); if(j+load[i].first<=K){ dp[i+1][j+load[i].first]=max(dp[i+1][j+load[i].first],dp[i][j]+load[i].second); } } } ll tot=0; auto dfs2=[&](auto f,int now,int pre,ll depth)->void{ bool flag=true; int res=0; for(edge e:G[now]){ if(e.to==pre) continue; flag=false; f(f,e.to,now,depth+e.cost); } if(flag){ //nowが根の場合のみ 足される tot+=depth; } return; }; dfs2(dfs2,0,-1,0); ll add=0; for(int j=0;j<=K;j++){ add=max(add,dp[N-1][j]); } ll ans=add+tot; cout<<ans<<endl; }