Codeforces Round #591 DIV1 C問題 (1250pt)
Codeforces Round #591 DIV2 E問題 (2250pt)
Technocup 2020 - Elimination Round 1 E問題 (2250pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, A[5d5], B[5d5], C[5d5], K;
wgraph<int> g;
ll dp[5d5], dpm[5d5];
ll gain[5d5];
{
int i, j, k, sz;
REP(rd_int()){
rd(N,K,(A--,B--,C)(N-1));
g.setEdgeRootedTree(N,N-1,A,B,C,0,1);
rrep(i,N){
sz = 0;
dp[i] = 0;
rep(j,g.es[i]){
k = g.edge[i][j];
dp[i] += dp[k];
gain[sz++] = dpm[k] - dp[k] + g.cost[i][j];
}
rsortA(sz, gain);
while(sz && gain[sz-1] <= 0) sz--;
dpm[i] = dp[i];
REP(j,min(sz,K)) dp[i] += gain[j];
REP(j,min(sz,K-1)) dpm[i] += gain[j];
}
wt(dp[0]);
}
}
Current time: 2024年04月25日22時21分48秒
Last modified: 2019年10月12日04時14分55秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF591 CF_Div1_C CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)