問題

問題概要

頂点数 $n$ の木が与えられる( $i(1 \le i \le n-1)$ 番目の辺は頂点 $u_i$ と $v_i$ を結ぶ)。隣接する頂点に移動するコストを1であるとすると、各頂点について、その頂点をスタート地点とした時に全ての頂点を訪れるための最小コストを求めよ。

$2 \le n \le 10^5$

アイデア

今回は、とある問題の想定解が全方位木dpだったので、その理解を多少はスムーズにできるように全方位木dp練習としてこの問題を解いた。

まずは、適当な根を決めて、根付き木とみなしてdfsをしながらその頂点に対する部分木の性質を得る。つまり、まずは0を根とした時のこの問題の解を求める。全ての頂点に訪れるという状況を考えると、根をスタート地点とするといくつかの部分木に分岐している。 $k$ 個の分岐がある時、 $k-1$ 個は分岐先に行って、全頂点を巡りまた根に戻ってくる必要があり、 $1$ 個は分岐先に行って、帰ってくる必要はない(その部分木内の全頂点を訪れた時点でstopできる)。

よって、1回目のdfsではこの2つの値を各頂点に対する部分木に対して求める。それが pair<int,int> dp1[N]となっている。帰ってくる必要がある場合の最小コスト、ない場合の最小コストをペアで保存する。ある場合は一意に決まる(各部分木の"ある場合のコスト"+2(行き帰りの分)の和になる)。ない場合は、"ない場合"に該当させる部分木を1つ選び、それ以外は"ある場合に"該当させるので、"ない場合"に該当させる部分木を全探索してその最小値を取れば良い。

そうすると、この問題に対して0を寝とした場合の解は求めることができたことになる(dp1[0].second)。

次に、この問題を全頂点に対して解く。任意の頂点 $x$ に対して、上と同じようなことを考えたいとすると、先程の0を根とした木の上で $x$ の部分木になっている部分についてはそのまま結果を利用してよいことになるが、新しく部分木として見なす必要があるのが $x$ の親方面に1つ出来ていると見ることが出来る。この親方面にできる部分木の情報を、子に渡しながら1回目のdfsと似たようなことを2回目のdfsで行う。

親方面にできる部分木の情報をどう渡していくかということになるが、部分木の情報なので、同様にpairで渡していく("ある場合"、"ない場合"のそれぞれのコスト)。今 $v$ にいて、次に進む子の方向が決まった時( $nx$ )、0を根とした根付き木上で $v$ の子になっている $nx$ 以外の部分木も、親方面にできる部分木の一員となるので、この情報を盛り込むことになる。

その調整をするために、「ある部分木を"ある場合"から"ない場合"に切り替えたらどれくらい得か」を計算しておくと、次に進む方向が一番得な方か否かで場合分けをして処理することが出来る。細かい内容はコメントで。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using pi = pair<int,int>;
const int N = 100000;

vector<int> G[N];

// 帰ってくる必要がある/ない
pi dp1[N];
void dfs(int v, int par)
{
    int res = 0;
    for(int nx:G[v])if(nx!=par)
    {
        dfs(nx,v);
        res += dp1[nx].fi+2;
    }

    int notback = res;
    for(int nx:G[v])if(nx!=par)
    {
        int t = res;
        t += dp1[nx].se+1 - (dp1[nx].fi+2);
        notback = min(notback,t);
    }

    dp1[v] = {res,notback};
}

int ans[N];
void dfs2(int v, int par, pi d)
{

    // vを根としてみた時に、全ての部分木の情報を持つ
    vector<pair<pi,int>> c;
    // 子ども方向
    for(int nx:G[v])if(nx!=par) c.pb({dp1[nx],nx});
    // 親方向
    c.pb({d,-1});

    int C = c.size();
    // 全部の部分木に対して、「行って帰ってくる」ことにした場合のコスト
    int sum = 0;
    rep(i,C) sum += c[i].fi.fi+2;

    // secondを選ぶことによって得られる利益(少ないほうが嬉しい)
    // (利益,頂点)
    vector<pi> gain;

    // 頂点vに対する答えを計算する
    ans[v] = sum;
    // どの部分木を"帰らない"にするか全探索
    rep(i,C)
    {
        // "帰ってくる"から"帰らない"に切り替えたことによって変動するコスト
        int g = c[i].fi.se+1 - (c[i].fi.fi+2);

        ans[v] = min(ans[v],sum+g);
        gain.pb({g,c[i].se});
    }

    // 親方向の部分木の情報 d を更新しながら、子に伝播させる
    sort(all(gain));
    rep(i,C)
    {
        int nx = gain[i].se;
        if(nx==-1) continue;

        pi nd;
        // "帰ってくる"時は、行き先の部分木のぶんを除けば良い
        nd.fi = sum - (dp1[nx].fi+2);

        // "帰らない"時は、行き先の部分木が切り替えが一番得かそうでないかで場合わけが発生する
        // 一番得なら、その部分木は"帰らない"をえらんでいるはずなので次点で得なところを"帰らない"に切り替える
        // そうでなければ一番得な部分木を"帰らない"にすれば良い
        nd.se = nd.fi;
        if(i==0)
        {
            if(C>1) nd.se += gain[1].fi;
        }
        else nd.se += gain[0].fi;

        dfs2(nx,v,nd);
    }
}

int main()
{
    int n;
    scanf(" %d", &n);
    rep(i,n-1)
    {
        int u,v;
        scanf(" %d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }

    dfs(0,-1);
    dfs2(0,-1,{-2,-1});
    rep(i,n) printf("%d\n", ans[i]);
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

AOJ 1595 - Traffic Tree

問題

問題概要

アイデア

実装(C++)