(木の直径の性質)AGC-005-C-Tree Restoring

問題URL→http://agc005.contest.atcoder.jp/tasks/agc005_c

木の直径の性質を使う問題。
木の直径は与えられた数列の最大値。
解説にある通り、dist(a,b)をa-b間の距離とすると、
dist(a,b)が木の直径となるとき、任意の頂点pとqについて
max(dist(p,q)) = max(dist(p,a), dist(p,b))となる。

つまり直径上にない点からの最も遠い距離はaまたはbまでの距離のマックスとなる。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N;
int a[110];
multiset<int> ms;

signed main()
{
    cin >> N;
    REP(i,N) {
        cin >> a[i];
        ms.insert(a[i]);
    }

    int K = *max_element(a, a + N);
    if (K % 2 == 0) {
        for (int i=K/2+1; i<=K; i++) if (ms.count(i) < 2) {
            cout << "Impossible" << endl;
            return 0;
        }
        for (int i=K/2+1; i<=K; i++) ms.erase(i);
        if (ms.count(K/2) == 1 && ms.size() == 1) {
            cout << "Possible" << endl;
            return 0;
        } else {
            cout << "Impossible" << endl;
            return 0;
        }
    } else {
        for (int i=(K+1)/2; i<=K; i++) if (ms.count(i) < 2) {
            cout << "Impossible" << endl;
            return 0;
        }
        for (int i=(K+1)/2+1; i<=K; i++) ms.erase(i);
        if (ms.count((K+1)/2) == 2 && ms.size() == 2) {
            cout << "Possible" << endl;
            return 0;
        } else {
            cout << "Impossible" << endl;
            return 0;
        }
    }
}

(木の直径・木DP)ARC-022-C-ロミオとジュリエット

問題URL→http://arc022.contest.atcoder.jp/tasks/arc022_3

知らない典型問題っぽかったのですぐ解説見た。
公式の解説の木DPが良く分からなかったので次のkmjpさんのブログを参考にした。
DFSを2回行うのが簡単らしいが木DPのほうが応用が利くらしい。

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
const int INF = 1e9;

int N;
int x, y;
vector<int> E[101010];
int sx, sy;
int ma;

pair<int, int> dfs(int cur, int pre)
{
    vector<pair<int, int>> V;

    REP(i,E[cur].size()) {
        int tar = E[cur][i];
        if (tar == pre) continue;
        V.push_back(dfs(tar, cur));
    }

    V.push_back(make_pair(1, cur));

    sort(V.begin(), V.end());
    reverse(V.begin(), V.end());
    if (V.size() >= 2) {
        int tar = V[0].first + V[1].first;
        if (tar > ma) {
            ma = tar;
            sx = V[0].second + 1;
            sy = V[1].second + 1;
        }
    }

    return make_pair(V[0].first + 1, V[0].second);
}

signed main()
{
    cin >> N;
    REP(i,N-1) {
        cin >> x >> y;
        x--; y--;
        E[x].push_back(y);
        E[y].push_back(x);
    }

    dfs(0, -1);
    cout << sx << " " << sy << endl;
}