Codeforces Round #591 DIV1 C問題/DIV2 E問題 - Paint the Tree

Source

Codeforces Round #591 DIV1 C問題 (1250pt)
Codeforces Round #591 DIV2 E問題 (2250pt)
Technocup 2020 - Elimination Round 1 E問題 (2250pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20191012-1）のコード

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月16日13時55分24秒
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)