大臣的旅费

大臣的旅费

题意

给定一颗树，要找到距离最远的两个点

解题思路

首先概念：

• 树的直径：先找到最远的点，然后再从这个点跑 dfs ，找最远距离。

代码

• 自己手糊的

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e5 + 10, inf = 1 << 30;

vector<PII> g[N];
int d[N];

void dfs(int u, int f) {
    for (auto &[v, w] : g[u]) {
        if (v == f) continue;
        d[v] = max(d[v], d[u] + w);
        dfs(v, u);
    }
}

int ans = 0;
void dfs2(int u, int f, int dist) {
    for (auto &[v, w] : g[u]) {
        if (v == f) continue;
        if (ans < dist + w) {
            ans = dist + w;
        }
        dfs2(v, u, dist + w);
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i ++ ) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    d[1] = 0;
    dfs(1, 0);
    int id = 0;
    int mx = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (d[i] > mx) {
            mx = d[i];
            id = i;
        }
    }
    dfs2(id, 0, 0);
    ll res = ans * 10 + 1ll * (1 + ans) * ans / 2;
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

• 看题解后修剪的
  • 感觉虽然复用性高了，但对于题目来说，感觉我写的感觉更便于理解（

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e5 + 10, inf = 1 << 30;

vector<PII> g[N];
int d[N];
int ans, idx;

void dfs(int u, int f, int dist) {
    for (auto &[v, w] : g[u]) {
        if (v == f) continue;
        if (ans < dist + w) {
            ans = dist + w;
            idx = v;
        }
        dfs(v, u, dist + w);
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i ++ ) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    d[1] = 0;
    dfs(1, 0, 0);
    dfs(idx, 0, 0);
    ll res = ans * 10 + 1ll * (1 + ans) * ans / 2;
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}