数的直径（两次DFS)

桃花

题目描述

桃花一簇开无主，可爱深红映浅红。

——《题百叶桃花》

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

输入描述:

第一行有一个正整数n，表示桃树的节点个数。
接下来n-1行，第i行两个正整数a,b

输出描述:

第一行一个整数，表示HtBest使用一次魔法棒最多可以摘到多少桃花。
输入

3

1 2

2 3
输出
3
题意：就是求数的直径，不过本题求的是顶点数,树的直径的一个性质：距某个点最远的叶子节点一定
是树的某一条直径的端点。这样我们先dfs求一个点的最远端点，再从这个点dfs一次。也可以百度一下，
大意是反证距离任意点最远的点都是直径的端点。
代码：

#include<iostream>

#include<string.h>

#include<algorithm>

#include<stdio.h>

#include<queue>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long long ll;

typedef pair<int,int> PII;

#define mod 1000000007

#define pb push_back

#define mp make_pair

#define all(x) (x).begin(),(x).end()

#define fi first

#define se second

//head

#define N 1000005

vector<int>V[N];

int dis[N];

int xp=-;

int ans=;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>'') {if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void write(int x)

{

     if(x<) putchar('-'),x=-x;

     if(x>) write(x/);

     putchar(x%+'');

}

void dfs(int a)

{

    if(xp<dis[a])

    {

        xp=dis[a];

        ans=a;

    }

    for(int v: V[a])

    {

        if(dis[v]==-)

        {

            dis[v]=dis[a]+;

            dfs(v);

        }

    }

}

int main()

{

    //ios_base::sync_with_stdio(0); cin.tie(0);

    int n;

    int a,b;

    n=read();

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

    {

       a=read();

       b=read();

       V[a].pb(b);

       V[b].pb(a);

    }

   for(int i=;i<=n;i++) dis[i]=-;

   dis[]=;

   dfs();

   memset(dis,-,sizeof(dis));

   dis[ans]=;

   xp=-;

   dfs(ans);

   write(xp+);

}

巴特西

数的直径（两次DFS)

题目描述

输入描述:

输出描述:

最新文章

热门文章