こっちも問題文が長い…。
https://codeforces.com/contest/1280/problem/D
問題
N頂点の木を成すグラフが与えられる。
各頂点vには、2つの値B[v],W[v]が設定されている。
このグラフをいくつかの連結成分に分けたとする。
連結成分内の頂点について、sum(B)<sum(W)となる連結成分は最大何個作れるか。
解法
dp(v,win) := 頂点vのSubTree以下で、vを含まないsum(B)<sum(W)となる連結成分がwin個あるとき、vを含む連結成分のsum(W)-sum(B)
このテーブルをDFS順に葉から埋めて行けばよい。
勝ち数を減らしてもsum(W)-sum(B)を改善させる必要はないので、sum(W)>sum(B)となった時点でどん欲に連結成分を区切ってしまってよい。
int T; int N,M; int B[3030],W[3030]; vector<int> E[3030]; vector<pair<int,ll>> conv(vector<pair<int,ll>> A,vector<pair<int,ll>> B) { int a=A.size(),b=B.size(); vector<pair<int,ll>> C(a+b,{-10000,0}); int x,y; FOR(x,a) FOR(y,b) { C[x+y+1]=max(C[x+y+1],{A[x].first+B[y].first+(B[y].second>0),A[x].second}); C[x+y]=max(C[x+y],{A[x].first+B[y].first,A[x].second+B[y].second}); } return C; } vector<pair<int,ll>> dfs(int cur,int pre) { vector<pair<int,ll>> V; V.push_back({0,W[cur]-B[cur]}); FORR(e,E[cur]) if(e!=pre) V=conv(V,dfs(e,cur)); return V; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>M; FOR(i,N) cin>>B[i]; FOR(i,N) cin>>W[i]; FOR(i,N) E[i].clear(); FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } auto v=dfs(0,0); cout<<v[M-1].first+(v[M-1].second>0)<<endl; } }
まとめ
Dの割には簡単?