Codeforces Global Round 2 F - Niyaz and Small Degrees

うくうく

codeforces.com

問題概要

頂点の木が与えられる. 各辺には重みが割り当てられている.

各 について, グラフの最大次数を 以下にするときに削除する辺の重みの和の最小値を求めよ.

解法

が固定されている場合について考える.

これは次のような木DPで求めることができる.

dp[idx][flag]:= 頂点idxを根の次数を ( flag) 以下にする(頂点idxの部分木内のすべての頂点の次数は 以下)ときの最小コスト. ここで flag は または .

つまりflagが0のとき の次数が , 1のとき である.

子どもたちの計算結果をマージして, dp[idx][flag] を計算できれば良い. 頂点 の次数を とすると, 次数を 以下にするためには頂点 から生える辺のうち 本だけ削除する必要がある. c に向かう辺を削除する場合は dp[c][1](次数が の計算結果なので c の親の辺は削除する必要がある), 辺を削除しない場合は dp[c][0] (次数が で 1 本余分がある) から計算できる.

えーこれを最小とする選び方はなんか dp[c][*] を適当な基準でソートすると最小値が求まる.

が固定ではない場合を考える. 次数が 以下の頂点については辺を消すことを要請しないのでほとんど考えなくても良くて, より大きい頂点を考えたい気持ちになる.

基本的には より大きいものからなる連結成分ごとに独立して木DPをしてその和を求めればよい. 計算量は次数の和に抑えられる.

xより大きい子へ向かう辺を何個削除するか固定する. すると 以下の頂点へ向かう辺を 本削除するときの最小コストみたいなのが必要になって, 昇順 個の和に答えられるデータ構造が必要になる. 貼るとできるので終わり(補足なんですが, が変化する回数が少ないので priority_queue を2つ持つとできる).

うくちゃんね

ソース

template< typename T >
struct PrioritySumStructure {
  static const bool INCREASE = false;
  static const bool DECREASE = true;

  bool order;
  int k, sz, all;
  T sum;
  set< pair< T, int > > add, pend;
  map< int, T > adding, pending;

  PrioritySumStructure(int k, bool order = INCREASE) : k(k), sum(0), sz(0), order(order) {}

  void sweep() {
    while(sz < k && !pend.empty()) {
      auto p = order ? --pend.end() : pend.begin();
      sum += p->first;
      ++sz;
      add.emplace(*p);
      adding.emplace(p->second, p->first);
      pending.erase(p->second);
      pend.erase(p);
    }
    while(sz > k) {
      auto p = order ? add.begin() : --add.end();
      sum -= p->first;
      --sz;
      pend.emplace(*p);
      pending.emplace(p->second, p->first);
      adding.erase(p->second);
      add.erase(p);
    }
  }

  T get_sum() {
    if(sz < k) throw ("Get Sum Exception");
    return sum;
  }

  void add_element(int k, T x) {
    if(adding.count(k) || pending.count(k)) {
      throw ("Add Element Exception");
    }
    ++sz;
    ++all;
    add.emplace(x, k);
    adding[k] = x;
    sum += x;
    sweep();
  }

  void delete_element(int k) {
    --all;
    if(pending.count(k)) {
      pend.erase({pending[k], k});
      pending.erase(k);
    } else if(adding.count(k)) {
      --sz;
      sum -= adding[k];
      add.erase({adding[k], k});
      adding.erase(k);
      sweep();
    } else {
      throw ("Delete Element Exception");
    }
  }

  void increment_size() {
    ++k;
    sweep();
  }

  void decrement_size() {
    if(k == 0) throw ("Decrement Size Exception");
    --k;
    sweep();
  }
};

int N, D;
WeightedGraph< int > g;
bool alive[250000];
vector< PrioritySumStructure< int64 > > pri;

pair< int64, int64 > dfs(int idx, int par) {
  alive[idx] = false;
  int64 all = 0;
  vector< int64 > val;
  for(auto &to : g[idx]) {
    if(to == par) {
      continue;
    } else if(alive[to]) {
      auto ret = dfs(to, idx);
      auto cost = min(ret.first, ret.second + to.cost);
      all += cost;
      val.emplace_back(ret.second + to.cost - cost);
    } else {
      break;
    }
  }

  sort(begin(val), end(val));

  int64 res[2] = {infll, infll};
  int deg = g[idx].size();
  if(~par) --deg;

  for(int i = 0; i < 2; i++) {
    int over = deg - D + 1 - i;
    int64 presum = 0;
    for(int j = 0; j <= min(over,(int)val.size()); j++) {
      int rest = over - j;
      if(rest <= pri[idx].all) {
        while(pri[idx].k < rest) pri[idx].increment_size();
        while(pri[idx].k > rest) pri[idx].decrement_size();
        chmin(res[i], presum + all + pri[idx].get_sum());
      }
      if(j < val.size()) presum += val[j];
    }
  }
  return {res[0], res[1]};
}


int main() {
  cin >> N;
  g.resize(N);
  for(int i = 1; i < N; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x, --y;
    g[x].emplace_back(y, z);
    g[y].emplace_back(x, z);
  }
  for(int i = 0; i < N; i++) {
    sort(g[i].begin(), g[i].end(), [&](auto p, auto q) {
      return g[p].size() > g[q].size();
    });
  }
  vector< int > uku[250000], kill[250001];
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < g[i].size(); j++) uku[j].emplace_back(i);
    kill[g[i].size()].emplace_back(i);
  }
  for(int i = 0; i < N; i++) {
    pri.emplace_back(PrioritySumStructure< int64 >(0));
  }
  for(int i = 0; i < N; i++) {
    for(auto &p : kill[i]) {
      for(auto &to : g[p]) pri[to].add_element(p, to.cost);
    }
    for(auto &p : uku[i]) alive[p] = true;
    D = i;
    int64 all = 0;
    for(auto &p : uku[i]) {
      if(alive[p]) all += dfs(p, -1).second;
    }
    cout << all << " ";
  }
  cout << endl;
}