树的中心

SPOJ PT07Z, Longest path in a tree

两遍 dfs 求树的中心

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

vector<int> e[N];
int n;
int dep[N];

void dfs(int u, int fa) {
    for (int to : e[u]) {
        if (to == fa) continue;
        dep[to] = dep[u] + 1;
        dfs(to, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    dfs(1, 0);
    int maxver = -1, maxx = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        if (maxx < dep[i]) {
            maxx = dep[i];
            maxver = i;
        }
    }

    memset(dep, 0, sizeof(dep));
    dfs(maxver, 0);

    cout << *max_element(dep + 1, dep + n + 1) << '\n';

    return 0;
}

树性 dp 求树的中心：·求出每个点往下走的最长链和次长链，答案就是所有的点的最长链和次长链的长度之和的最大值。

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = 20010;

struct edge {
    int to, next;
} e[M];

int head[N], idx = 1;

void add(int u, int v) {
    idx++, e[idx].to = v, e[idx].next = head[u], head[u] = idx;
}

int fzmax[N], fcmax[N];

void dfs(int u, int fa) {
    for (int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if (to == fa) continue;
        dfs(to, u);
        int d = fzmax[to] + 1;
        if (d > fzmax[u]) {
            fcmax[u] = fzmax[u];
            fzmax[u] = d;
        }
        else if (d > fcmax[u]) fcmax[u] = d;
    }
}

int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    memset(fzmax, 0, sizeof(fzmax));
    memset(fcmax, 0, sizeof(fcmax));
    dfs(1, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, fzmax[i] + fcmax[i]);
    cout << ans << '\n';
    return 0;
}

性质：如果所有边权都为正数，那么所有直径的重点都是一个点。

例题

CF911F Tree Destruction

先标记树的直径，然后将除了直径之外的点删除，将它们到直径两端的最大值累加到答案中。最后将直径一点点删掉就可以了。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 200010;
const i64 INF = 0x3f3f3f3f;

int n;
vector<int> e[N];
int dep1[N], dep2[N];
int f[N];
bool path[N];
int out[N];

void dfs(int u, int fa, int *dep) {
    f[u] = fa;
    for (int to : e[u]) {
        if (to == fa) continue;
        dep[to] = dep[u] + 1;
        dfs(to, u, dep);
    }
}

i64 res;
vector<pair<int, pair<int, int> > > ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        out[u]++, out[v]++;
    }
    dfs(1, 0, dep1);
    int maxx = -INF, root = -1;
    for (int i = 1; i <= n; i++) {
        if (maxx < dep1[i]) {
            maxx = dep1[i];
            root = i;
        }
    }
    memset(dep1, 0, sizeof(dep1));
    dfs(root, 0, dep1);
    int maxver = -1;
    maxx = -INF;
    for (int i = 1; i <= n; i++) {
        if (maxx < dep1[i]) {
            maxx = dep1[i];
            maxver = i;
        }
    }

    int v = maxver;
    while (v != f[root]) {
        path[v] = true;
        v = f[v];
    }
    
    dfs(maxver, 0, dep2);

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (path[i]) continue;
        if (out[i] == 1) {
            // cout << i << endl;
            q.push(i);
        }
    }

    while (q.size()) {
        int t = q.front();
        q.pop();
        if (path[t]) continue;

        for (int to : e[t]) {
            if (path[to]) continue;
            out[to]--;
            if (out[to] == 1) q.push(to);
        }

        if (dep1[t] < dep2[t]) {
            res += dep2[t];
            ans.push_back({maxver, {t, t}});
        }
        else {
            res += dep1[t];
            ans.push_back({root, {t, t}});
        }
    }

    v = root;
    while (v != maxver) {
        res += dep2[v];
        ans.push_back({maxver, {v, v}});
        v = f[v];
    }
    cout << res << '\n';
    for (auto x : ans) cout << x.first << ' ' << x.second.first << ' ' << x.second.second << '\n';
    return 0;
}

树的重心