牛客小白月赛6 C 桃花

C 桃花

题目：

链接：https://www.nowcoder.com/acm/contest/136/C
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述
    桃花一簇开无主，可爱深红映浅红。

                                        ——《题百叶桃花》

    桃花长在桃树上，树的每个节点有一个桃花，调皮的HtBest想摘尽可能多的桃花。HtBest有一个魔法棒，摘到树上任意一条链上的所有桃花，由于HtBest法力有限，只能使用一次魔法棒，请求出Htbest最多可以摘到多少个桃花。

输入描述:
第一行有一个正整数n，表示桃树的节点个数。
接下来n-1行，第i行两个正整数a
_i
,b
_i
 ，表示桃树上的节点a
_i
,b
_i
之间有一条边。
输出描述:
第一行一个整数，表示HtBest使用一次魔法棒最多可以摘到多少桃花。
示例1
输入
复制
3
1 2
2 3
输出
复制
3
示例2
输入
复制
3
1 2
1 3
输出
复制
3
示例3
输入
复制
4
1 2
2 3
3 4
输出
复制
4
备注:
对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

思路：

求树的直径，可以用两遍dfs或者bfs求，第一次：先从任意一个起点开始搜到离该点最远的点，第二次：再从第一次找到的最远的点开始搜，找到离这个点最远的点，这两点之间的距离就是树的直径。

注意：dfs TLE 了，最好用bfs

代码：

BFS:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 1e6+20;
int N,l,r,cnt,pos,ans;
int first[maxn],nx[2*maxn];
int q[maxn],de[maxn];
bool used[maxn];

struct maple{
    int f,t;
}Rode[2*maxn];

void Build(int f,int t)
{
    Rode[++cnt]=(maple){f,t};
    nx[cnt]=first[f];
    first[f]=cnt;
}
void Bfs(int k)
{
    memset(used,0,sizeof(used));
    memset(de,0,sizeof(de));
    int head=0,tail=1;
    used[k]=1;
    q[tail]=k;
    while(head<tail)
    {
        ++head;
        int a=q[head];
        for(int i=first[a];i;i=nx[i])
           if(!used[Rode[i].t])
           {
                  used[Rode[i].t]=1;
                  de[Rode[i].t]=de[a]+1;
                  q[++tail]=Rode[i].t;
           }
    }
    pos=q[head] ; ans=de[pos];
}

int main()
{
    scanf("%d",&N);
    for(int i=1;i<N;++i)
    {
        scanf("%d%d",&l,&r);
        Build(l,r);
        Build(r,l);
    }
    Bfs(1);
    Bfs(pos);
    printf("%d",ans+1);
    return 0;
}

DFS(TLE):

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e6+20;
 
 
vector<int> edge[maxn];
 
int mx = 1, id=0;
int dis[maxn];
 
void dfs(int pos, int v){
    dis[pos] = v;
    if(v>mx){
        id = pos;
        mx = v;
    }
    for(int i=0;i<edge[pos].size();i++){
        int to = edge[pos][i];
        if(dis[to]==0)
         dfs(to,v+1);
    }
}
 
 
int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(1,1);
    memset(dis,0,sizeof(dis));
    mx = 1;
    dfs(id,1);
    printf("%d
",mx);
 
    return 0;
}