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

· · 题解

看了其他的题解，大部分(quan)都是用DFS+LCA过的。这里我提供一种最短路的思路。（主要还是因为不想写LCA）

首先，我们来看这样的一棵二叉树 （就是原题的）

现在要求查询这棵树的深度，其实就是这棵树上到根节点的最长距离+1；查询这棵树的宽度，其实就是到根节点距离相同的节点个数的最大值

例如这棵树，不难发现，8,9,10 到根节点的距离最大，为 3 （注意断句） ，depth=3+1=4

其次，4,5,6,7 到根节点的距离都是 2 ，width=4

那么如何处理第三个问题呢？

我们建的树是双向边 （废话），这里我们做一个巧妙的处理——将由 u->v 的边权赋为1，反向边赋为2。为什么呢？我们来看下面这两张图（为求清晰而分开）——

例如，我们要求 8->4 距离，这时最短路算法一定会找到 LCA(8,4)=2

为什么呢？因为如果不是公共祖先，两顶点将无法到达；而如果不是最近的，例如我们找到了 1 ，它一定比到 2 的路径多 3 。所以，建图时只要 fa->x 为 1，x->fa 为 2，就可以用一次最短路求解。

那么此时对于前两个操作有无影响呢？肯定是没有的。因为求前两个操作的最短路时，都是从根节点出发的，只会经过数值为1的边，而不会绕回去。

综上，只要建含边权的双向边，跑两遍最短路，就可以解决问题了（源点分别是1,u，用桶统计一下即可）

那么时间复杂度就是Dijkstra:O(nlogn) 或 SPFA:O(玄学)

当然，这应该是个稀疏图，从理论上和实际测试中(n=100000)中SPFA都胜于Dijkstra（SPFA: 我还活着）且算法表现也较为优异（和最优解比较，也许是电脑比较快 ）

下面当然就是喜闻乐见的代码了：

#include<bits/stdc++.h>
#define in(x) x=read()
using namespace std;
const int maxN=1000;
inline int read()
{
    int n=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) {n=n*10+ch-'0'; ch=getchar();}
    return n;
}
struct Node{int to,next,value;}edge[2*maxN];
int dis[maxN+1],vis[maxN+1],head[maxN+1],tot,box[maxN+1];
void addedge(int x,int y,int w) {edge[++tot]={y,head[x],w}; head[x]=tot;}
void SPFA(int s)
{
    queue<int>q; q.push(s);
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    vis[s]=1; dis[s]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop(); vis[x]=0;
        for(int i=head[x];i;i=edge[i].next)
            if(dis[edge[i].to]>dis[x]+edge[i].value)
            {
                dis[edge[i].to]=dis[x]+edge[i].value;
                if(!vis[edge[i].to])
                {
                    vis[edge[i].to]=1;
                    q.push(edge[i].to);
                }
            }
    }
}
int n,u,v,ans;
int main()
{
    in(n);
    for(int i=1;i<n;i++)
    {
        in(u); in(v);
        addedge(u,v,1); addedge(v,u,2);
    }
    in(u); in(v); SPFA(1);
    for(int i=1;i<=n;i++) box[dis[i]]++,ans=max(ans,dis[i]);
    printf("%d\n",ans+1); ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,box[i]);
    printf("%d\n",ans);
    SPFA(u); printf("%d\n",dis[v]);
    return 0;
}

完结撒花QwQ，如有错误欢迎指出，不胜感激 （毕竟这算法是脑补出来的）