CF 120F Spider 树的直径 简单题

一个男孩有n只玩具蜘蛛，每只蜘蛛都是一个树的结构，现在男孩准备把这n只小蜘蛛通过粘贴节点接在一起，形成一只大的蜘蛛。大的蜘蛛也依然是树的结构。输出大的蜘蛛的直径。

知识：

树的直径是指树上的最长简单路

求树的直径有个结论：

假设s-t这条路径为树的直径，或者称为树上的最长路。

从任意一点u出发搜到的最远的点一定是s、t中的一点，然后再从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜或者深搜就可以找出树的最长路

证明：反证法。

那回到这道题，要使得大蜘蛛的直径最大，就要使连接的小蜘蛛都是用s，t2个点来和其他蜘蛛连接

所以大蜘蛛的直径就是小蜘蛛的直径的和

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int maxn=;

 const int inf=0x3f3f3f3f;

 struct Edge

 {

     int to,next;

 };

 Edge edge[maxn<<];

 int head[maxn];

 int tot;

 bool vis[maxn];

 struct Point

 {

     int num,dis;

 };

 void init()

 {

     memset(head,-,sizeof head);

     tot=;

 }

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].next=head[u];

     head[u]=tot++;

 }

 //返回树的直径

 int solve(int m);

 //返回结构体，树的节点和节点到u的距离

 Point bfs(int u,int m);

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     int n;

     scanf("%d",&n);

     int ans=;

     for(int i=;i<=n;i++)

     {

         init();

         int m;

         scanf("%d",&m);

         for(int i=;i<m;i++)

         {

             int u,v;

             scanf("%d %d",&u,&v);

             addedge(u,v);

             addedge(v,u);

         }

         ans+=solve(m);

     }

     printf("%d\n",ans);

     return ;

 }

 int solve(int m)

 {

     Point cnt=bfs(,m);

     Point ret=bfs(cnt.num,m);

     return ret.dis;

 }

 Point bfs(int s,int m)

 {

     memset(vis,false,sizeof vis);

     Point start;

     start.num=s;

     start.dis=;

     vis[s]=true;

     queue<Point>que;

     while(!que.empty())

         que.pop();

     que.push(start);

     Point ret;

     while(!que.empty())

     {

         Point u=que.front();

         que.pop();

         if(que.empty())

         {

             ret.num=u.num;

             ret.dis=u.dis;

         }

         for(int i=head[u.num];~i;i=edge[i].next)

         {

             int v=edge[i].to;

             if(vis[v])

                 continue;

             Point uu;

             uu.num=v;

             uu.dis=u.dis+;

             vis[v]=true;

             que.push(uu);

         }

     }

     return ret;

 }