题解 P3884 【[JLOI2009]二叉树问题】

· · 题解

看了一下发现大家都是 LCA 做的。

我这里给大家提供一种使用 Floyd 算法的做法。

树其实一种特殊的图。

即没有环路，一定联通，而且有且有只有一个节点没有入度的图。

那么树上任意两点间的距离可以直接通过最短路算法获得。

树的深度就是距离根节点最远的那个点的距离。

树的宽度是节点最多的一层，同一层的节点距离根节点的距离都是相同的，所以也可以直接枚举获得。

Floyd 算法应该是相当基础的算法，我相信大佬们应该都会。

代码：

#include<bits/stdc++.h>
#define r read()//偷懒
#define lnf INT_MAX/4
// INT_MAX 是一个常量定义在 limits.h 头文件中 其值就是字面意思
#define Min(a,b) ((a)<(b)?(a):(b))//手打min提高效率
#define Max(a,b) ((a)>(b)?(a):(b))//同上，切记括号千万不能漏
//STL 中的 max 和 min 速度相当慢 用 if 速度也不及条件表达式
using namespace std;
inline int read()//快读不解释
{
    char c=getchar();
    int x=0,fh=0;
    while(c<'0'||c>'9'){fh|=c=='-';c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return fh?-x:x;
}
int n=r;
int a[101][101];//邻接矩阵存图
int b[100000000];
int main()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
           if(i!=j)a[i][j]=lnf;//预处理
    for(int i=1;i<n;i++)
    {
        int x=r,y=r;
        a[x][y]=1;//父亲到孩子距离为1
        a[y][x]=2;//孩子到父亲距离为2
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                 a[i][j]=Min(a[i][j],a[i][k]+a[k][j]);//Floyd算法
    int u=r,v=r;
    int maxsum=0,maxd=0,maxn=1;
    for(int i=2;i<=n;i++)
    {
        maxsum=Max(maxsum,a[1][i]);//深度
        b[a[1][i]]++;//同时统计每一层的节点数
        maxn=Max(maxn,a[i][1]);
    }
    for(int i=1;i<=maxn;i++)
        maxd=Max(maxd,b[i]);//宽度
    cout<<maxsum+1<<endl;
    cout<<maxd<<endl;
    cout<<a[u][v]<<endl;//树上距离
    return 0;
}