题解 P3174 【[HAOI2009]毛毛虫】

· · 题解

一看这道题立马想到了树的直径

还没有两遍dfs求树的直径的做法，赶快来水一发

已经会树的直径的大佬可以跳过这一段qwq

树的直径：树上最长的一条链

具体求法有两种，一种是树形DP，这里就不细讲了，我着重讲下两遍dfs求树的直径的做法，可以说很经典了。

做法： 先从任意一点出发，找到离出发点的最远点，然后再从找到的那个点出发，找一次最远点，这两点就是树的直径的两个端点。

以下是证明（也不是必须会证明啦，不想看的dalao可以跳过）

![](https://cdn.luogu.com.cn/upload/image_hosting/tv0ekb3y.png) ------------ 接下来回到这道题，跟树的直径是不是就有点联系了，树的直径的$dfs$的时候每延申$1$个点，我们只需要加上$1$个长度，而这道题应该这样加： 假设我们$dfs$从$x$开始，那么我们一开始初始的总和为$dis[x]$（$dis$为这个点连到的所有点），设$nx$为$x$的儿子，那么往$nx$展的时候，应该加上$dis[nx]-2$，因为当搜到$nx$的时候，首先他自己这个点，已经被他的父亲$x$加过了，而且$nx$还连了一个$x$，$x$被父亲自己加过了，所以不需要再加了，所以减$2

思路讲完了，下面是代码时间~

#include <bits/stdc++.h>
using namespace std;
int n , m , ans1 , ans2 , maxx , tot , f = 0;   //ans1为第一次的最远点，ans2为第二次的最远点 
int dis[300010];
vector<int> e[300010]; 
stack<int> s;
void dfs1(int x , int sum , int fa){
    if(maxx < sum){
        maxx = sum;
        ans1 = x;
    }
    for(int i = 0; i < e[x].size(); i++){
        int nx = e[x][i];
        if(nx == fa) continue;
        dfs1(nx , sum + dis[nx] - 2 , x);
    }
} 
void dfs2(int x , int sum , int fa){
    if(tot < sum){
        ans2 = x;
        tot = sum;
    }
    for(int i = 0; i < e[x].size(); i++){
        int nx = e[x][i];
        if(nx == fa) continue;
        dfs2(nx , sum + dis[nx] - 2 , x);
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) dis[i]++;   //自己也算连到了 
    for(int i = 1; i <= m; i++){
        int x , y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
        dis[x]++;
        dis[y]++;
    }
    dfs1(1 , dis[1] , 0);
    dfs2(ans1 , dis[ans1] , 0);
    cout << tot;
    return 0;
}