P3884 [JLOI2009]二叉树问题

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;i++)
#define maxn 202
using namespace std;
int now,head[maxn],n,m,s,d[maxn],deep[maxn],p[maxn][11],maxx;
struct node{
    int a,b,next;
}e[maxn];
inline void add(int u,int s)
{
    e[++now].a=u;
    e[now].b=s;
    e[now].next=head[u];
    head[u]=now;
} emmm链式前向星存图标准代码了解一下
inline void dfs(int k,int fa)
{
    d[k]=d[fa]+1;子节点的层数只其父节点层数+1
    deep[k]=d[k];
    maxx=max(maxx,d[k]);统计最大层数
    p[k][0]=fa;
    for(int i=1;(1<<i)<=d[k];i++)
    {
        p[k][i]=p[p[k][i-1]][i-1];倍增的关键!!!
    }
    for(int i=head[k];i;i=e[i].next)
    {
        int b=e[i].b;
        if(b!=fa) dfs(b,k); 如果没有处理过,就跑一边 dfs的思想
    }
}倍增标准预处理
inline int lca(int a,int lp)
{
    if(d[a]>d[lp]) swap(a,lp);
    for(int i=10;i>=0;i--)因为数据很水便只开了10就够用了
    {
        if(d[a]<=d[lp]-(1<<i))
        {
            lp=p[lp][i];先让两个点的层数爬到一起
        }
    }
    if(a==lp) return a;
    for(int i=10;i>=0;i--)
    {
        if(p[a][i]!=p[lp][i])
            a=p[a][i],lp=p[lp][i];然后就是两个点一起爬树
    }
    return p[a][0];因为现在都是相等的所以随便输出哪一个都可以了
}
int main()
{
    int maxl=0,cs[105]={0},x,y;
    scanf("%d",&n);
    For(i,1,n-1)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x); 无向图别忘了
    }    
    dfs(1,0);
    scanf("%d%d",&x,&y);
    For(i,1,n) cs[deep[i]]++;统计宽度
    For(i,1,maxx) maxl=max(maxl,cs[i]);
    printf("%d\n%d\n",maxx,maxl);
    int kjk=lca(x,y);
    printf("%d\n",(d[x]-d[kjk])*2+(d[y]-d[kjk]));emmm这里是因为数据水到都是先父节点再子节点所以我就懒得打一个max函数了,只要记得乘以二就可以了
    return 0;
}
上一篇:Android 自定义ViewGroup,实现侧方位滑动菜单


下一篇:[算法模板]线性基