src/old/TreeDiameter.hpp

• View this file on GitHub
• Last update: 2020-06-13 20:39:55+09:00
• Include: #include "src/old/TreeDiameter.hpp"

Code

// 木の直径がdiameterに格納される
signed main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int diameter = 0;
    function<int(int, int)> dfs = [&](int v, int p) {
        int ma = 0;
        for (int s : g[v])
            if (s != p) {
                int tmp = dfs(s, v) + 1;
                diameter = max(diameter, ma + tmp);
                ma = max(ma, tmp);
            }
        return ma;
    };
    dfs(0, -1);
}

#line 1 "src/old/TreeDiameter.hpp"
// 木の直径がdiameterに格納される
signed main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int diameter = 0;
    function<int(int, int)> dfs = [&](int v, int p) {
        int ma = 0;
        for (int s : g[v])
            if (s != p) {
                int tmp = dfs(s, v) + 1;
                diameter = max(diameter, ma + tmp);
                ma = max(ma, tmp);
            }
        return ma;
    };
    dfs(0, -1);
}

Back to top page