もうひとつの全方位木DP

なにもかくことがないね（えーん）

もうひとつの全方位木DPなんですが、任意の全方位木DPが記述できるかは確認してない(多分できないと思う(うく))ので期待はしないでね　ゴメンネ

この記事は Competitive Programming (2) Advent Calendar 2018 の20日目の記事です。

ei1333.hateblo.jp

※ 辺視点のほうが考えやすいので、辺視点で考えます。

頂点1を根とする根付き木があって、各辺についてDPの計算に必要な値が求まっているとします（根に向かう辺の値だけあればよい）。

下図のように別の頂点（今回は頂点 ${2}$ ）に根をうつしたときの木について求めたい場合は、もともとの木の根から離れる辺の値についての値をトップダウンに求めていきます。矢印の先が、それが指す頂点からみたときの辺の値を示すこととします。 f:id:ei1333:20181220211424p:plain

この操作により、頂点 ${2}$ から生えるすべての辺についての値が求まっているので、答えを求めることが可能です。

以前の記事では思考停止アルゴリズムと書きましたが、2回目のDFSでトップダウンに求めるときに根を変える操作をどうするかをすこしだけ考える必要がありました。そこでこれを改善したいと思います。

とりあえず頂点 ${1}$ から再帰関数を愚直に呼び出すこととして、計算済みの（有向）辺の値は再計算する必要がないのでメモ化しておくことを考えます。このとき、以下のような流れで処理が行われると思います。赤字で示したnewはメモ化されていなかったのではじめて計算したことを表します。また青矢印は計算のために使うべき辺、灰矢印は計算に不要な辺を表します。

えー頂点7と8も同様にやりますが図の作成に飽きたため

次のような問題を考えます。

${N}$ 頂点の木が与えられます。それぞれの頂点について、最も遠い頂点までの距離を求めてください。

これをさっき述べたような方法でやろうとすると次のようなコードになると思います。

#include <bits/stdc++.h>

using namespace std;

int N;
vector< int > g[100000];
map< int, int > dp[100000];

int dfs(int idx, int par) {
  if(dp[idx].count(par)) return dp[idx][par];
  int ret = 0;
  for(auto &to : g[idx]) {
    if(to == par) continue;
    ret = max(ret, dfs(to, idx) + 1);
  }
  return dp[idx][par] = ret;
}

int main() {
  cin >> N;
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for(int i = 0; i < N; i++) {
    cout << dfs(i, -1) << endl;
  }
}

これで全方位木DP終わり！ｗみたいな気持ちになりたいんですが、このコードだと計算量が破滅してしまいます。メモ化される値の個数自体は辺の数に抑えられるので ${O(N)}$ なんですが、例えばスターグラフなど次数が大きい頂点がある場合などに遷移がそれぞれ ${O(N)}$ かかってこわれます。データセット弱いと案外通るかも　通らないか

結局、次数が多い頂点がある場合にすべての辺を見直すことをたくさんやってしまうことが非効率的です。これは多くの場合（子と子のマージが二項演算で定義できる場合？）効率的に求めることができます。

具体的にはこれをします（ありがとうございます！）。

オレンジの部分の計算は「a で b 以下を切ったときの準同型」の値で，これが効率的に計算できるかどうかは問題依存．逆元がとれるなら簡単に O(1)．最大値とかは上位 2 件覚えておけば OK．汎用的なのは子を２項演算で潰すタイプで，セグ木を作ると O(d log d)．
— ™ 🔰 (@tmaehara) 2018年4月2日

えーさっき示したメモ化再帰の各頂点の辺の値を表す配列はそれぞれ以下のようになっています。

f:id:ei1333:20181220221700p:plain

このうち親の辺の値を取り除いたものを知りたいです(-1の場合は何も取り除かない)。

if(to == par) continue;

に相当

下の図の赤い矢印が親の辺の値だとすると、左右から親の手前まで伸ばした辺の値の範囲の演算結果が求めたいものです。

f:id:ei1333:20181220222226p:plain

結局左右それぞれからの累積和的な配列があれば ${O(1)}$ で求めることができます。

ここからは抽象化を考えます。

木DPはある頂点を計算する時に

その頂点のDP配列の初期化(単位元 ${ident}$ とする)
子頂点のDP配列を辺を通して持ち上げて( ${f2}$ とする)、DP配列と ${f2}$ の結果をマージする(関数 ${f1}$ とする)ことをすべての子について行う

をします（えーこのへんは宗教的な何かを感じるので適当に解釈し直してください＞＜）この実装だと ${f2}$ で持ち上げるときに、その頂点からパスが生える場合とかもそこで考慮する必要があるので注意してください。

最後にそれぞれの頂点についてそのDP配列より答えを計算します。

ソースコードは以下に示しました。

template< typename Data, typename T >
struct ReRooting {
 
  struct Node {
    int to, rev;
    Data data;
  };
 
  using F1 = function< T(T, T) >;
  using F2 = function< T(T, Data) >;
 
  vector< vector< Node > > g;
  vector< vector< T > > ldp, rdp;
  vector< int > lptr, rptr;
  const F1 f1;
  const F2 f2;
  const T ident;
 
  ReRooting(int n, const F1 &f1, const F2 &f2, const T &ident) :
      g(n), ldp(n), rdp(n), lptr(n), rptr(n), f1(f1), f2(f2), ident(ident) {}
 
  void add_edge(int u, int v, const Data &d) {
    g[u].emplace_back((Node) {v, (int) g[v].size(), d});
    g[v].emplace_back((Node) {u, (int) g[u].size() - 1, d});
  }
 
  void add_edge_bi(int u, int v, const Data &d, const Data &e) {
    g[u].emplace_back((Node) {v, (int) g[v].size(), d});
    g[v].emplace_back((Node) {u, (int) g[u].size() - 1, e});
  }
 
 
  T dfs(int idx, int par) {
 
    while(lptr[idx] != par && lptr[idx] < g[idx].size()) {
      auto &e = g[idx][lptr[idx]];
      ldp[idx][lptr[idx] + 1] = f1(ldp[idx][lptr[idx]], f2(dfs(e.to, e.rev), e.data));
      ++lptr[idx];
    }
    while(rptr[idx] != par && rptr[idx] >= 0) {
      auto &e = g[idx][rptr[idx]];
      rdp[idx][rptr[idx]] = f1(rdp[idx][rptr[idx] + 1], f2(dfs(e.to, e.rev), e.data));
      --rptr[idx];
    }
    if(par < 0) return rdp[idx][0];
    return f1(ldp[idx][par], rdp[idx][par + 1]);
  }
 
  vector< T > solve() {
    for(int i = 0; i < g.size(); i++) {
      ldp[i].assign(g[i].size() + 1, ident);
      rdp[i].assign(g[i].size() + 1, ident);
      lptr[i] = 0;
      rptr[i] = (int) g[i].size() - 1;
    }
    vector< T > ret;
    for(int i = 0; i < g.size(); i++) {
      ret.push_back(dfs(i, -1));
    }
    return ret;
  }
};

dfs関数では尺取りっぽく左右からの累積和配列を構築しています。

ここからは以前の全方位木DPの記事に対応した問題を解いていくことにします.

例題その 1

根を通るパスの長さの最長 = 根から最も遠い頂点までの距離 + 異なる部分木で次に根から遠い頂点までの距離でした.

要するに部分木のパスの長さの top2 の距離を持っておけばよいです.

2019/03/31 修正　vectorじゃなくてpairで2つ持つほうがいいね

int main() {
  int N;
  cin >> N;

  using pi = pair< int, int >;
  const int INF = 1 << 30;

  auto f1 = [](pi a, pi b) {
    for(auto &t : {b.first, b.second}) {
      if(a.first < t) {
        a.second = a.first;
        a.first = t;
      } else if(a.second < t) {
        a.second = t;
      }
    }
    return a;
  };
  auto f2 = [](pi a, int d) {
    return pi(max(0, a.first) + d, -INF);
  };

  ReRooting< int, pi > g(N, f1, f2, pi(-INF, -INF));
  for(int i = 1; i < N; i++) {
    int s, t, w;
    cin >> s >> t >> w;
    g.add_edge(s, t, w);
  }

  int ret = 0;
  for(auto &p : g.solve()) {
    ret = max(ret, p.first);
    ret = max(ret, p.first + p.second);
  }
  cout << ret << endl;
}

例題その 2

最も遠い葉までの距離を求めたくて、やります

int main() {
  int N, D;
  cin >> N;

  auto f1 = [](int a, int b) {
    return max(a, b);
  };

  auto f2 = [](int a, int data) {
    return a + data;
  };

  ReRooting< int, int > g(N, f1, f2, 0);
  for(int i = 1; i < N; i++) {
    int s, t;
    cin >> s >> t;
    --s, --t;
    g.add_edge(s, t, 1);
  }
  for(auto &p : g.solve()) {
    cout << (N - 1) * 2 - p << endl;
  }
}

これはうまくかけるね

例題その 3

最も遠い葉までの距離と反転する辺の個数の合計みたいなのをもとめたいです。

const int INF = 1 << 30;
using pi = pair< int, int >;
 
int main() {
  int N, D;
  cin >> N >> D;
 
  auto f1 = [](pi a, pi b) {
    return pi(a.first + b.first, max(a.second, b.second));
  };
  auto f2 = [](pi a, pi data) {
    a.first += data.second;
    a.second += data.first;
    return a;
  };
 
  ReRooting< pi, pi > g(N, f1, f2, {0, 0});
  for(int i = 1; i < N; i++) {
    int s, t, w;
    cin >> s >> t >> w;
    --s, --t;
    g.add_edge_bi(s, t, pi(w, true), pi(w, false));
  }
 
  int ret = INF;
  for(auto &p : g.solve()) {
    if(p.second <= D) ret = min(ret, p.first);
  }
  if(ret >= INF) ret = -1;
  cout << ret << endl;
}

うく

例題4

子頂点(子頂点自身は含まない)以下の期待値の和(first)と部分木の頂点数(second)を持っておきます。

${f2}$ では子頂点が0個の場合に0除算が起こるので場合分けが必要です。

using pi = pair< double, int >;

int main() {
  int N, D;
  cin >> N;

  auto f1 = [](pi a, pi b) {
    return pi(a.first + b.first, a.second + b.second);
  };

  auto f2 = [](pi a, int data) {
    return pi((a.second == 0 ? 0.0 : a.first / a.second) + 1.0, 1);
  };

  ReRooting< int, pi > g(N, f1, f2, {0.0, 0});
  for(int i = 1; i < N; i++) {
    int s, t;
    cin >> s >> t;
    --s, --t;
    g.add_edge(s, t, 0);
  }

  for(auto &p : g.solve()) {
    cout << fixed << setprecision(10) << (p.second == 0 ? 0.0 : p.first / p.second) << endl;
  }
}

[2019/12/30 追記] 実装について

下の実装のほうが使いやすいです！！！！！！build()するとそれぞれの頂点を根としたときのDP配列が返ってきます. また副作用として、グラフ g の各頂点 v から生える辺 Edge について、頂点 v を根としたときに部分木頂点 to から辺を使って持ち上げてきた値が dp に入ります.

template< typename sum_t, typename key_t >
struct ReRooting {
  struct Edge {
    int to;
    key_t data;
    sum_t dp, ndp;
  };

  using F = function< sum_t(sum_t, sum_t) >;
  using G = function< sum_t(sum_t, key_t) >;

  vector< vector< Edge > > g;
  vector< sum_t > subdp, dp;
  const sum_t ident;
  const F f;
  const G gg;

  ReRooting(int V, const F f, const G g, const sum_t &ident)
      : g(V), f(f), gg(g), ident(ident), subdp(V, ident), dp(V, ident) {}

  void add_edge(int u, int v, const key_t &d) {
    g[u].emplace_back((Edge) {v, d, ident, ident});
    g[v].emplace_back((Edge) {u, d, ident, ident});
  }

  void add_edge_bi(int u, int v, const key_t &d, const key_t &e) {
    g[u].emplace_back((Edge) {v, d, ident, ident});
    g[v].emplace_back((Edge) {u, e, ident, ident});
  }

  void dfs_sub(int idx, int par) {
    for(auto &e : g[idx]) {
      if(e.to == par) continue;
      dfs_sub(e.to, idx);
      subdp[idx] = f(subdp[idx], gg(subdp[e.to], e.data));
    }
  }

  void dfs_all(int idx, int par, const sum_t &top) {
    sum_t buff{ident};
    for(int i = 0; i < (int) g[idx].size(); i++) {
      auto &e = g[idx][i];
      e.ndp = buff;
      e.dp = gg(par == e.to ? top : subdp[e.to], e.data);
      buff = f(buff, e.dp);
    }
    dp[idx] = buff;
    buff = ident;
    for(int i = (int) g[idx].size() - 1; i >= 0; i--) {
      auto &e = g[idx][i];
      if(e.to != par) dfs_all(e.to, idx, f(e.ndp, buff));
      e.ndp = f(e.ndp, buff);
      buff = f(buff, e.dp);
    }
  }

  vector< sum_t > build() {
    dfs_sub(0, -1);
    dfs_all(0, -1, ident);
    return dp;
  }
};

最後に

別の全方位木DPの書き方を紹介しました　ほかに書くことがなかったからね

えー実用性なく内科

たぴちゃんたべてやる

おわりです

図について

パワーポイントでつくっていたんですが15回くらい応答なしになって落ちて非常につらい気持ちになった

エディタについて

WindowsでやるときにはCLionをつかっています。ICPCのアジア予選でも使いました(今年から使えるようになった？)。

CLionの機能についてあんまり知らないんですが、よくつかっているやつを列挙します。

Live Templates
いわゆるスニペットです。下の図のように登録しておくと、その名前を打ってTABを押すと展開されます。

f:id:ei1333:20181220235955p:plain

STLに略称をつけたりするときにも使えます(lower_bound→lb, uq→unique(～) みたいな)

Refactor
変数名とかを右クリックするとメニューに生えます。変数の一括置換みたいなことをしたいときにつかえます。
コード整形
これはね、そう
コピーとか切り取りとかショートカットキー
これもね、そうあんまりしらない
全選択＆コピーみたいなのができるようになっていて、ABCのAのFAをとりたいときとかにたまにやくだつ
デバッガ
優秀なデバッガがついてるみたい
バグらないのでつかったことがありません

ほかにもあるかも　あきたのでやめます

うぃーんﾋﾞｰﾄﾋﾞｰﾄひるどwwwwwwうっくっくwwwwwwえいえいえt(←いずらいt)いえいwwwwらて。について

これはなんですか

うぃーんﾋﾞｰﾄﾋﾞｰﾄひるどwwwwwwうっくっくwwwwwwえいえいえt(←いずらいt)いえいwwwwらて。
— うし (@ei1333) 2017年3月17日

元ネタはこれです　深夜テンションやめてくれ

きらっ☆について

おはよっ　きらっ☆
— タプリス(競プロ) (@ei13333) 2018年7月9日

元ネタはこれです　何

たぴちゃんについて

twitter.com

たぴちゃんってよばれているみたいです

誰

うしについて

たべられません

最後に

ねね

ei1333の日記

ぺこい