题意描述

图中有$n$个点，每两点间只有唯一的路径，对于这样一个给定的图，最大的“毛毛虫”会有多大。

毛毛虫包含一条主链，毛毛虫中的节点，要不在主链上，要么和主链上某节点相邻，如下图所示有两只合法的毛毛虫，点数越多，毛毛虫越大。

输入格式

输入文件第一行两个整数$n$，$m$。
　　
接下来M行，每行两个整数$a, b$，表示从$a$到$b$有一条边相连

输出格式

一个整数$ans$,表示最大的毛毛虫的大小。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围与约定

对于$20\%$的数据，$n≤200$

对于$40\%$的数据，$n≤5 \times 10^3$

对于$100\%$的数据，$n≤10^6$

保证两点之间只有一条路径。

分析

~~第一眼看到这题我以为是个神仙$DP$，结果发现是个zz题目~~

咳咳，首先由两点之间只有一条路经可以看出，题目给出的是一棵树。

而题目要求我们求一条最长的”毛毛虫”，实质上就是求出一条树上最长链。

但在这题中，每个点对答案的贡献不是$1$，而是与其相连的点的个数。

因此，我们需要先进行一遍$dfs$，搜索出这棵树的根节点（即点权最大的节点），之后以根节点为起点寻找树上最长链。

两遍$dfs$即可。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 1000001

using namespace std;

int n , m;

struct Edge{
    int to;
    int last;
}edge[N << 1];

int edge_num;
int head[N << 1];

I void add_edge(int from , int to){
    edge[++ edge_num] = (Edge){to , head[from]};
    head[from] = edge_num;
}

bool vis[N];
ll dis[N];
int ans , root;

void search(int x , int d , bool flag){
    vis[x] = true;
    for(int i = head[x]; i ; i = edge[i].last){ //枚举每一条出边
        int to = edge[i].to;
        if(!vis[to]){      
            vis[to] = true;
            if(flag == true){   
                search(to , d + dis[to] , false);
            }
            else{//如果不是起始点，则从上一个点到达这个点的路径会被计算两次。因此要-1
                search(to , d + dis[to] - 1 , false);
            }
        }
    }
    if(d > ans){    //若当前节点的权值大于根节点，则更新根节点。
        ans = d;
        root = x;
    }
}

int main(){
    int u , v;
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= m; i ++){
        scanf("%d%d" , &u , &v);
        add_edge(u , v);
        add_edge(v , u);
        dis[u] ++  , dis[v] ++;
    }
    search(1 , 1 , true);   //第一遍dfs寻找根节点
    for(int i = 1; i <= n; i ++){
        vis[i] = false;
    }
    ans = 0;
    search(root , 1 , true);    //第二遍dfs寻找树上最长链
    printf("%d" , ans);

    return 0;
}