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

· · 题解

这道题目还是比较水的，N很小，只有100，于是我就又用链表来水这道题，还1遍A掉了，后来看了一下已有的题解，发现没有用链表做的，所以我又来水了。

其实我的链表完全可以用数组替代的，我只不过想炫(zhuang)耀(bi)一下才用的。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{
    node *f;//完全可以只用一个父节点
    int deep;
};
node *root,*p,*q,*address[101];//address是储存每一个地址的
int n,x,y,u,v,ans,maxdeep,maxwide,deep[101];//maxdeep代表最大深度，maxwide代表最大宽度，deep储存每一个深度有多少个节点
int main(){
    scanf("%d",&n);
    root=new node,root->f=NULL,root->deep=1;//第一个节点没有父节点
    address[1]=root;//这是第一个节点的地址
    for(int i=2;i<=n;++i){
        scanf("%d%d",&x,&y);
        p=new node,p->f=address[x];//address就是来偷懒的，否则还要O(n)的时间来搜索
        p->deep=p->f->deep+1;
        address[y]=p;//把x设为y的父节点并且加入y的地址
    }scanf("%d%d",&u,&v);//压一下行，应该没关系
    for(int i=1;i<=n;++i)
        ++deep[address[i]->deep],maxdeep=max(maxdeep,address[i]->deep);//统计每一个深度节点的个数，并更新最大深度
    for(int i=1;i<=maxdeep;++i)
        maxwide=max(maxwide,deep[i]);//更新最大深度
    printf("%d\n%d\n",maxdeep,maxwide),p=address[u],q=address[v];
    while(p->deep>q->deep)
        p=p->f,ans+=2;
    while(p->deep<q->deep)
        q=q->f,++ans;//这4行把p节点和q节点弄到同一深度
    while(p!=q)
        p=p->f,q=q->f,ans+=3;//同时往上爬，答案加3
    printf("%d",ans);
    return 0;
}