樹直徑

給一顆 \(n\) 點的樹，求樹直徑

\(n\le 2\times 10^5\)

兩次 dfs code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
vector<int> G[MAXN];

int x = 0;
int mx = 0;
void dfs(int u, int par, int dist) {
    if (dist > mx) {
        mx = dist;
        x = u;
    }
    for (int v : G[u]) {
        if (v == par) continue;
        dfs(v, u, dist + 1);
    }
}

void solve() {
    int n;
    cin >> n;
    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);
    }

    dfs(0, -1, 0);
    mx = 0;
    dfs(x, -1, 0);

    cout << mx << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
}

dp code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e6;

int n, ans = 0, h[maxn], dp[maxn];
vector<int> G[maxn];

void dfs(int u, int par) {
    int mx = 0, sec = 0;
    for (auto v : G[u]) {
        if (v == par) continue;
        dfs(v, u);

        if (dp[v] > mx) {
            sec = mx;
            mx = dp[v];
        } else if (dp[v] > sec) {
            sec = dp[v];
        }
    }
    dp[u] = mx + 1;
    ans = max(ans, mx + sec);
}

signed main() {
    cin >> n;
    int u, v;
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 1);
    cout << ans << "\n";
}

若邊權有負，要用樹 dp，不能用兩次 DFS

題目¶

這篇 CF Blog 上面的

CF 1085 D.A Wide, Wide Graph

給一顆有 \(n\) 個點的樹

定義 \(G_k\) 為 : 有幾個點 \(u\) 至少存在一個點與他距離 \(\ge k\)

依序求 \(G_1,\ldots,G_n\)

\(n\le 10^5\)

思路

我們只要求出對於每個點，與他距離最遠的點的距離即可

code

#include <bits/stdc++.h>
#define int long long
#define s second
#define f first
#define pii pair<int,int>
using namespace std;

const int INF = 0x3f3f3f3f, MAXN = 1e5 + 5, M = 1e9 + 7;
int t, n, m, dis[MAXN], mx[MAXN];
vector<vector<int>> G(MAXN);

int dfs(int u, int p, int d) {
    int ans = u;
    dis[u] = max (d, dis[u]);

    for (auto v : G[u]) {
        if (v != p) {
            int tmp = dfs(v, u, d + 1);

            if (dis[tmp] > dis[ans]) {
                ans = tmp;
            }
        }
    }

    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    t = 1;

    while (t--) {
        cin >> n;

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

        int s = dfs(1, 0, 0);
        int t = dfs(s, 0, 0);
        dfs(t, 0, 0);

        sort(dis + 1, dis + 1 + n);
        int x = 0;

        for (int i = 1; i <= n; i++) {
            while (x <= n && dis[x] < i) {
                x++;
            }

            if (x > n)
                cout << n << " ";
            else
                cout << x << " ";
        }
    }
}

2020 TOI pB.建設人工島

給 \(n\) 個點，邊有權重的樹，求嚴格次長樹直徑

\(n\le 10^5\)

思路

利用樹 dp 找樹直徑的方法，只是多保留當前次長得即可

code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 2e18;
const int MAXN = 1e5 + 5;
const int M = 1e9 + 7;

struct Node {
    int mx, sec;
};

int n, m;
vector<pair<int, int>> G[MAXN];
vector<Node> dp(MAXN);
int vis[MAXN];
Node ans;

void cal(int val, Node &x) {
    if (x.mx < val) {
        x.sec = x.mx, x.mx = val;
    } else if (val != x.mx && x.sec < val) {
        x.sec = val;
    }
}

void dfs(int u) {
    vis[u] = true;
    for (auto [v, w] : G[u]) {
        if (vis[v] == 1) continue;

        dfs(v);
        // ans 的轉移式
        cal(dp[v].mx + dp[u].mx + w, ans);
        cal(dp[v].mx + dp[u].sec + w, ans);
        cal(dp[u].mx + dp[v].sec + w, ans);

        // update dp[u]
        cal(dp[v].mx + w, dp[u]);
        cal(dp[v].sec + w, dp[u]);
    }
}

signed main() {
    cin >> n;
    int u, v, w;
    for (int i = 1; i <= n - 1; i++) {
        cin >> u >> v >> w;
        u++, v++;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    dfs(1);
    cout << ans.sec << "\n";
}

CF 1294 F. Tree Paths on a Tree

給你一顆 \(n\) 個點的樹，選相異三個點 \(a, b, c\)，使得至少有包含 \(a,b,c\) 其中兩個的 path 數量最大，輸出最大 path 數量和 \(a,b,c\)。

\(3\le n\le 2\times 10^5\)

思路

其中兩點一定是樹直徑的兩端點。剩下一個點如何確定？到兩個點距離合最大即可，在兩次 bfs 過程中保留兩個端點到任意點的距離然後找這個最大值就好

或者也可以找到樹直徑兩端 s, t，將樹用 s 重新定根，求每個點 u 與 LCA(u, t) 的距離即可

參考自 : https://newcoder-glm.blog.csdn.net/article/details/104080663?ydreferer=aHR0cHM6Ly9ibG9nLmNzZG4ubmV0Lw%3D%3D