dfs
1、dfs的同时 “往下” 维护信息（使用参数，维护当前距离根节点的距离，每一个分支都有一个递增的距离，如果使用全局变量，需要在递归后进行恢复，如以下第二段代码）。
2、一边遍历一边维护并更新全局需要的最远距离，和最远距离的点的编号。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 5, M = 2 * N;
int n;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int max_d_id = 0;//维护一个全局的距离u最远的点
long long max_d = 0;
void dfs(int u, long long d)//遍历每个点的同时，维护最远距离的点的编号和最远距离， d 是当前距离
{
st[u] = 1;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
int k = w[i];
if(!st[j])
{
if((long long)(d + k) > max_d)
{
max_d = d + k;
max_d_id = j;
}
dfs(j, d + k);
}
}
}
// int dfs_d(int u)//返回距离u最远的 点 的距离
// {
// st[u] = 1;
// int max_d = 0;//默认距离自己最远的点的距离0
// for(int i = h[u]; i != -1; i = ne[i])
// {
// int j = e[i];
// int k = w[i];
// if(!st[j])
// {
// int d = dfs_d(j) + k;
// if(d > max_d)
// {
// max_d = d;
// }
// }
// }
// return max_d;
// }
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
dfs(1, 0);//得出距离任意一点的 距离最远的点
memset(st, 0, sizeof st);
max_d = 0;
dfs(max_d_id, 0);//得出树的直径
long long sum = 0;
for(int i = 1; i <= max_d; i++)//max_id 最大1e8，累加可能超过int
{
sum += 10 + i;
}
printf("%lld", sum);
return 0;
}
使用全局变量来维护当前的距离，注意恢复现场,对比使用函数传参，略微复杂
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 5, M = 2 * N;
int n;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// int max_d_id = 0;//维护一个全局的距离u最远的点
// long long max_d = 0;
// void dfs(int u, long long d)//遍历每个点的同时，维护最远距离的点的编号和最远距离， d 是当前距离
// {
// st[u] = 1;
// for(int i = h[u]; i != -1; i = ne[i])
// {
// int j = e[i];
// int k = w[i];
// if(!st[j])
// {
// if((long long)(d + k) > max_d)
// {
// max_d = d + k;
// max_d_id = j;
// }
// dfs(j, d + k);
// }
// }
// }
int max_d_id = 0;//维护一个全局的距离u最远的点
long long max_d = 0;
long long d = 0;//使用全局变量维护当前距离
void dfs(int u)//遍历每个点的同时，维护最远距离的点的编号和最远距离
{
st[u] = 1;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
int k = w[i];
if(!st[j])
{
d = d + k;
if(d > max_d)
{
max_d = d;
max_d_id = j;
}
dfs(j);
d = d - k;//距离也要 恢复
}
}
}
// int dfs_d(int u)//返回距离u最远的 点 的距离
// {
// st[u] = 1;
// int max_d = 0;//默认距离自己最远的点的距离0
// for(int i = h[u]; i != -1; i = ne[i])
// {
// int j = e[i];
// int k = w[i];
// if(!st[j])
// {
// int d = dfs_d(j) + k;
// if(d > max_d)
// {
// max_d = d;
// }
// }
// }
// return max_d;
// }
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
dfs(1);//得出距离任意一点的 距离最远的点
memset(st, 0, sizeof st);
max_d = 0;
dfs(max_d_id);//得出树的直径
long long sum = 0;
for(int i = 1; i <= max_d; i++)//max_id 最大1e8，累加可能超过int
{
sum += 10 + i;
}
printf("%lld", sum);
return 0;
}
bfs
1、维护一个队列，保存 边 的信息（id, d）(编号，距离)
2、bfs向下遍历的同时，维护一个 d[]数组（表示距离根结点的距离） （区分dfs，在每个分支都会是一种情况，这是dfs的参数是会自动恢复现场的，保证每个分支只会计算每个分支自己的情况，而bfs则没有dfs这种恢复现场的特性，因此使用 数组d[]额外的空间，来同时记录每个分支各自的情况）。
3、一边遍历一边维护并更新全局需要的最远距离，和最远距离的点的编号。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 5, M = 2 * N;
typedef pair<int, int> PII;
#define x first
#define y second
int n;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int max_d_id = 0;
int max_d = 0;
int d[N];//用于维护距离根节点的距离
//初始化队列-维护每条 边 的信息
PII q[M]; int hh = 0, tt = -1;
void bfs(int u, int ud)
{
hh = 0, tt = -1;//更新
st[u] = 1;
q[++tt] = {u, ud};
d[u] = ud;
while(hh <= tt)
{
auto t = q[hh++];
int id = t.x, dd = t.y;
for(int i = h[id]; i != -1; i = ne[i])
{
int j = e[i], k = w[i];
if(!st[j])
{
st[j] = 1;
q[++tt] = {j, k};
//更新距离和点编号相关信息；
d[j] = d[id] + k;
//cout << u << "-" << j << ":" << d[j] << endl;
if(d[j] > max_d)
{
max_d = d[j];
max_d_id = j;
}
}
}
}
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
bfs(1, 0);//获取距离根节点1的最远的点的编号
memset(d, 0, sizeof d);//重新初始化
memset(st, 0, sizeof st);
max_d = 0;//重新初始化
bfs(max_d_id, 0);//获取树的直径
long long sum = 0;
for(int i = 1; i <= max_d; i++)//max_id 最大1e8，累加可能超过int
{
sum += 10 + i;
}
printf("%lld", sum);
return 0;
}
