例题网址：

https://www.acwing.com/problem/content/description/1209/

树形DP

用数组模拟

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int h[N], ne[N * 2], e[N * 2], v[N * 2], idx;//无向图，开二倍空间
int d[N];
bool vis[N];
int ans;

void tree_dp(int x){
    vis[x] = true;
    for(int i = h[x]; ~i; i = ne[i]){
        int y = v[i];
        if(vis[y]) continue;
        tree_dp(y);
        ans = max(ans, d[x] + d[y] + e[i]);
        d[x] = max(d[x], d[y] + e[i]);
    }
}

void add(int a, int b, int w){
    e[idx] = w;
    v[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
        add(b, a, w);
    }
    tree_dp(1);
    printf("%lld\n", ans * 10 + (ans * (ans + 1ll ) >> 1));
    return 0;
}

用vector模拟

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

typedef pair<int, long long> pii;

const int N = 1e5 + 10;
long long d[N];
bool vis[N];
long long ans;
vector<pii> city[N];

void tree_dp(int x){
    vis[x] = true;
    for(int i = 0; i < city[x].size(); i++){
        int y = city[x][i].first;
        if(vis[y]) continue;
        tree_dp(y);
        ans = max(ans, d[x] + d[y] + city[x][i].second);
        d[x] = max(d[x], d[y] + city[x][i].second);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        city[a].push_back({b, w});
        city[b].push_back({a, w});
    }
    tree_dp(1);
    printf("%lld\n", ans * 10 + (ans * (ans + 1ll ) >> 1));
    return 0;
}

两次DFS用结构体存（速度会慢）（还不如用Vector）

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int h[N], idx;//无向图，开二倍空间
int d[N];
bool vis[N];
int ans, maxu;

struct edge{
    int to;
    int ne;
    int w;
}e[N * 2];


void add(int a, int b, int w){
    e[idx].to = b;
    e[idx].ne = h[a];
    e[idx].w = w;
    h[a] = idx++;
}

void dfs(int u, int fa, int w){
    for(int i = h[u]; ~i; i = e[i].ne){
        int j = e[i].to;
        if(j != fa)
            dfs(j, u, w + e[i].w);
    }
    if(ans < w){
        maxu = u;
        ans = w;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
        add(b, a, w);
    }
    dfs(1, -1, 0);
    dfs(maxu, -1, 0);
    printf("%lld\n", ans * 10 + (ans * (ans + 1ll ) >> 1));
    return 0;
}

两次DFS用多个数组存（速度更快）

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int h[N], ne[N * 2], e[N * 2], v[N * 2], idx;//无向图，开二倍空间
int d[N];
bool vis[N];
int ans, maxu;

void add(int a, int b, int w){
    e[idx] = w;
    v[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u, int fa, int w){
    for(int i = h[u]; ~i; i = ne[i]){
        int j = v[i];
        if(j != fa)
            dfs(j, u, w + e[i]);
    }
    if(ans < w){
        maxu = u;
        ans = w;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
        add(b, a, w);
    }
    dfs(1, -1, 0);
    dfs(maxu, -1, 0);
    printf("%lld\n", ans * 10 + (ans * (ans + 1ll ) >> 1));
    return 0;
}