题意描述
图中有$n$个点,每两点间只有唯一的路径,对于这样一个给定的图,最大的“毛毛虫”会有多大。
毛毛虫包含一条主链,毛毛虫中的节点,要不在主链上,要么和主链上某节点相邻,如下图所示有两只合法的毛毛虫,点数越多,毛毛虫越大。
![合法的毛毛虫.png](/img/loading.gif)
输入格式
输入文件第一行两个整数$n$,$m$。
接下来M行,每行两个整数$a, b$,表示从$a$到$b$有一条边相连
输出格式
一个整数$ans$,表示最大的毛毛虫的大小。
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{ 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); for(int i = 1; i <= n; i ++){ vis[i] = false; } ans = 0; search(root , 1 , true); printf("%d" , ans);
return 0; }
|
THE END