- 两次 DFS
首先从任意节点y开始进行第一次DFS，到达距离其最远的节点，记为 z，然后再从 z 开始做第二次 DFS，到达距离z’最远的节点，记为 z’，则 z与z’之间距离即为树的直径。显然，如果第一次 DFS 到达的节点 z 是直径的一端，那么第二次 DFS 到达的节点 z’ 一定是直径的一端。
const int N = 10000 + 10;
int n, c, d[N];
vector<int> E[N];
void dfs(int u, int fa) {
for (int v : E[u]) {
if (v == fa) continue;
d[v] = d[u] + 1;
if (d[v] > d[c]) c = v;
dfs(v, u);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
E[u].push_back(v), E[v].push_back(u);
}
dfs(1, 0);
d[c] = 0, dfs(c, 0);
printf("%d\n", d[c]);
return 0;
}
模板题 https://www.luogu.com.cn/problem/B4016
两次dfs或bfs对于负权边不满足
2. 树形 DP
我们记录当 1 为树的根时，每个节点作为子树的根向下，所能延伸的最长路径长度 d1 与次长路径（与最长路径无公共边）长度 d2，那么直径就是对于每一个点，该点d1+d2能取到的值中的最大值。
int n, d = 0;
int d1[N], d2[N];
vector<int> E[N];
void dfs(int u, int fa) {
d1[u] = d2[u] = 0;
for (int v : E[u]) {
if (v == fa) continue;
dfs(v, u);
int t = d1[v] + 1;
if (t > d1[u])
d2[u] = d1[u], d1[u] = t;
else if (t > d2[u])
d2[u] = t;
}
d = max(d, d1[u] + d2[u]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
E[u].push_back(v), E[v].push_back(u);
}
dfs(1, 0);
printf("%d\n", d);
return 0;
}
其他方法
我们定义 dp[u]：以u为根的子树中，从u出发的最长路径。那么容易得出转移方程：dp[u] = max(dp[u], dp[v] + w(u,v))，其中的 v 为 u 的子节点，w(u,v)表示所经过边的权重。对于树的直径，实际上是可以通过枚举从某个节点出发不同的两条路径相加的最大值求出
const int N = 10000 + 10;
int n, d = 0;
int dp[N];
vector<int> E[N];
void dfs(int u, int fa)
{
for (int v : E[u])
{
if (v == fa) continue;
dfs(v, u);
d = max(d, dp[u] + dp[v] + 1);
dp[u] = max(dp[u], dp[v] + 1);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d %d", &u, &v);
E[u].push_back(v), E[v].push_back(u);
}
dfs(1, 0);
printf("%d\n", d);
return 0;
}
巡逻
https://www.acwing.com/problem/content/submission/352/
如果不建立新的道路，那么从 1 号节点出发，把整棵树上的每条边遍历至少一次，再回到 1 号节点，会恰好经过每条边两次，n个节点有n-1条边，路线总长度为 2 * (n - 1),建立1条新道路之后会生成环，因为新道路必须经过恰好一次，所以在沿着新道路(x,y)之后，要返回x，就必须沿着树上从y到x的路径巡逻一边，形成一个环，与不建立新道路的情况相结合，相当于树上x与y之间的所有路径就都只需经过一次。因此当k=1时，我们找到树的最长链，在两个端点之间加一条新道路，就能让总的巡逻距离最小。若树的直径为d，答案就是 2 * (n - 1) - d + 1。
加入第二条道路后，会形成一个新环，可能会与原环重叠。如果不重叠则按第一条路思路，减去重边。否则，在两个环重叠的情况下如果我们还按照刚才的方法把第2个环与建立1条新道路的情况相结合，两个环重叠的部分就不会被巡逻到。由于每条道路都必须被巡逻，我们就不得不让巡逻车在适当的时候重新巡逻这些环中未重叠的边，并且返回。最终结果是两个环未重叠的部分由只需经过一次变回了需要经过两次。重边多跑一次，所以重边边权设为-1;
# include <bits/stdc++.h>
using namespace std;
# define int long long
int n,k;
const int N=1e5+10,M=N*2;
int h[N], e[M], ne[M],w[M],idx;
int d[N],l;
int p[N],d2;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a],w[idx]=1,h[a] = idx ++ ;
}
void update(int ed, int st) //从 ed 回推到 st，并将路上经过的边都取反
{
while(ed != st)
{
w[p[ed]] = -1; //正向边取反
w[p[ed] ^ 1] = -1; //反向边取反
ed = e[p[ed] ^ 1]; //退到这条边的入点，即上一步走到的点
}
}
void dp(int u, int father) //树形dp求树的直径
{
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == father) continue;
dp(j, u);
d2 = max(d2, d[u] + d[j] + w[i]);
d[u] = max(d[u], d[j] + w[i]);
}
}
void dfs(int u,int fa)
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa)
continue;
d[j]=d[u]+1;
p[j]=i;
if(d[j]>d[l])
l=j;
dfs(j,u);
}
}
signed main()
{
cin>>n>>k;
memset(h,-1,sizeof h);
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1,-1);
int p=l;
memset(d,0,sizeof d);
dfs(l,-1);
int q=l;
int x=2*(n-1)-d[q]+1;
if(k==1)
cout<<x;
else
{
update(q,p);
memset(d,0,sizeof d);
dp(1,-1);
cout<<x-d2+1;
}
return 0;
}
大臣的旅费
# include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=2*N;
int h[N], e[M], w[M], ne[M], idx;
int n;
int d1[N],k1,k2,d2[N];
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u,int fa,int res)
{
d1[u]=res;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa)
continue;
dfs(j,u,res+w[i]);
}
}
void dfss(int u,int fa,int res)
{
d2[u]=res;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
//cout<<j<<" ";
if(j==fa)
continue;
dfss(j,u,res+w[i]);
}
}
signed main()
{
cin>>n;
memset(h, -1, sizeof h);
for(int i=1;i<=n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
dfs(1,-1,0);
int ans=0;
for(int i=1;i<=n;i++)
if(d1[i]>ans)
{
ans=d1[i];
k1=i;
}
//cout<<k1<<endl;
ans=0;
dfss(k1,-1,0);
for(int i=1;i<=n;i++)
if(d2[i]>ans)
{
ans=d2[i];
k2=i;
}
//cout<<ans<<endl;
cout<<(11+ans+10)*ans/2;
return 0;
}
