D47【模板】树的直径 B4016 树的直径

// 树的直径 正边权 两次DFS O(n)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300005;
int n, p;
LL d[N];
vector<pair<int, int>> G[N];

void dfs(int u, int fa)
{
	if (d[p] < d[u])
		p = u; // 记录直径端点
	for (auto [v, w] : G[u])
		if (v != fa)
		{
			d[v] = d[u] + w; // 记录从根到v的距离
			dfs(v, u);
		}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1, x, y, w; i < n; i++)
	{
		cin >> x >> y >> w;
		G[x].emplace_back(y, w);
		G[y].emplace_back(x, w);
	}
	d[1] = 0;
	dfs(1, 0);
	d[p] = 0; // p是直径的一个端点
	dfs(p, 0);
	cout << d[p]; // p是直径的另一个端点
	return 0;
}

代码1（d1数组+d2数组）：

#include <bits/stdc++.h> 
using namespace std;
const int N = 5e5 + 10;
vector<pair<int, int>> G[N];
int d1[N], d2[N], ans;
// d1[i]表示以i为出发点向下最长路径 
// d2[i]表示以i为出发点向下第二长路径 
void dfs(int x, int xfa)
{
    for (auto i : G[x]) if (i.first != xfa)
    {
        int y = i.first, c = i.second;
        dfs(y, x);
        if (d1[y] + c > d1[x]) d2[x] = d1[x], d1[x] = d1[y] + c;
        else if (d1[y] + c > d2[x]) d2[x] = d1[y] + c;
    }
    ans = max(ans, d1[x] + d2[x]);
}
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1, x, y, c; i < n; ++i)
    {
        scanf("%d%d%d", &x, &y, &c);
        G[x].push_back({ y, c }); G[y].push_back({ x, c });
    }
    memset(d1, 0, sizeof(d1)); memset(d2, 0, sizeof(d2)); 
    ans = 0; dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}

代码2（只有d数组）：

#include <bits/stdc++.h> 
using namespace std;
const int N = 5e5 + 10;
vector<pair<int, int>> G[N];
int d[N], ans;
void dfs(int x, int xfa)
{
    for (auto i : G[x]) if (i.first != xfa)
    {
        int y = i.first, c = i.second;
        dfs(y, x);
        ans = max(ans, d[x] + d[y] + c);
        d[x] = max(d[x], d[y] + c);
    }
}
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1, x, y, c; i < n; ++i)
    {
        scanf("%d%d%d", &x, &y, &c);
        G[x].push_back({ y, c }); G[y].push_back({ x, c });
    }
    memset(d, 0, sizeof(d));
    ans = 0; dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}