Educational Codeforces Round 74 F. The Maximum Subtree (R2300)

木 DP シリーズ！！！

問題へのリンク

問題概要

区間グラフとは、 個の区間が与えられたときに、各区間を各頂点に対応させ、intersection がある区間同士に辺が張られたようなグラフのことである。

さて、 頂点の木が与えられる。この木の連結な部分グラフ (それ自体も木になる) であって、区間グラフでもあるようなものの最大サイズを求めよ。

制約

• 

考えたこと

まずは「区間グラフであって木であるもの」がどのような性質を持つかを考えよう。少し考えるとそれは

• どの頂点についても直径からの距離が 1 であるような木

であるということがわかる。よって直径を求める感じの要領で木DPをしてあげることで答えを求めることができる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

long long rec(int v, int p, long long &res) {
    vector<long long> chs;
    for (auto e : G[v]) {
        if (e == p) continue;
        chs.push_back(rec(e, v, res) + max(0, (int)G[e].size()-2));
    }
    sort(chs.begin(), chs.end(), greater<long long>());
    if (chs.size() == 0) return 1;
    else if (chs.size() == 1) chmax(res, chs[0] + 1);
    else chmax(res, chs[0] + chs[1] + (int)G[v].size() - 1);
    return chs[0] + 1;
}

int main() {
    int T; cin >> T;
    for (int _ = 0; _ < T; ++_) {
        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);
        }
        long long res = 0;
        rec(0, -1, res);
        cout << res << endl;
    }
}