AOJ 1595 Traffic Tree (AUPC 2016 day2-I)

全方位木 DP の練習も兼ねて

問題へのリンク

問題概要

頂点数 のツリーが与えられる。ツリーの各頂点 に対して、 から出発して全頂点を訪れるまでに通る辺の本数の最小値を求めよ。

制約

• 

解法 1： 全方位木 DP

1 つの根についての答えなら普通の木 DP で求めることができる。今回は全頂点を根とした場合の答えを要求されているので、全方位木 DP が活躍しそうである。

普通の木 DP は

• 根を 1 つ固定したときの
• 各頂点を根とする部分根付き木についての問題を部分問題とした DP

であるのに対し、全方位木 DP は

• すべての辺 (u, v) に対して、
• 辺 (u, v) でツリーを分断してできる木 (u, v 側双方) についての問題を部分問題とした DP

である。

問題の言い換え

問題を扱いやすいように言い換える。問題は

• 各頂点 について
• を根としてできる部分木において、 からの深さの最大値を として
• が答え

となることがわかる (最も深いところで終わるのがよいことから)。ここまでくると、典型的な全方位木 DP となっている。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

using Graph = vector<vector<int>>;
int N;
Graph G;

vector<vector<long long>> dp;
long long rec(int v, int p = -1) {
    int s = G[v].size();
    long long res = 0;
    dp[v].assign(s, -1);
    for (int i = 0; i < s; ++i) {
        int to = G[v][i];
        if (to == p) continue;
        dp[v][i] = rec(to, v);
        chmax(res, dp[v][i] + 1);
    }
    return res;
}

void rerec(int v, long long pval = 0, int p = -1) {
    int s = G[v].size();
    for (int i = 0; i < s; ++i) {
        int to = G[v][i];
        if (to == p) {
            dp[v][i] = pval;
            continue;
        }
    }
    vector<long long> left(s+1, -1), right(s+1, -1);
    for (int i = 0; i < s; ++i) {
        left[i+1] = max(left[i], dp[v][i]);
        right[i+1] = max(right[i], dp[v][s-i-1]);
    }
    for (int i = 0; i < s; ++i) {
        int to = G[v][i];
        if (to == p) continue;
        rerec(to, max(left[i], right[s-i-1]) + 1, v);
    }
}

void solve() {
    dp.assign(N, vector<long long>());
    rec(0);
    rerec(0);
    for (int v = 0; v < N; ++v) {
        long long res = 0;
        for (int i = 0; i < G[v].size(); ++i) {
            chmax(res, dp[v][i] + 1);
        }
        cout << (N-1)*2 - res << endl;
    }
}

int main() {
    cin >> N;
    G.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    solve();
}

解法 2： 直径

直径に着目して解くこともできる。直径を一つ求めて、それぞれの頂点について、

• 直径中のどの頂点から出ている部分木の中にいるか
• その頂点からの深さはどれだけか

を求めておくことで、全クエリに答えることができる。