• P3884 [JLOI2009]二叉树问题


    ---------------------

    链接:Miku

    ---------------------

    这一道题只需要在倍增lca的板子上改一改就可以了。

    宽度和深度可以在倍增lca的dfs预处理的时候判断一下就可以,至于最后问的两点之间的距离

    首先需要求出两点公共祖先的位置,然后计算他们深度的差,并且按照题目要求分别处理即可

    --------------------

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int head[2*500001];
    int p;
    int md;
    int mk;
    int wei[10000];
    struct b{
        int to;
        int ne;
    } e[2*500001];
    int fa[2*500001][30];
    int dep[2*500001];
    int n,m,s;
    int logg[2*500001];
    int x,y;
    void dfs(int now,int fat){
        dep[now]=dep[fat]+1;
        md=max(md,dep[now]);
        wei[dep[now]]++;
        mk=max(mk,wei[dep[now]]);
        fa[now][0]=fat;
        for(int i=1;(1<<i)<=dep[now];++i){
            fa[now][i]=fa[fa[now][i-1]][i-1];
        }
        for(int i=head[now];i;i=e[i].ne){
            if(e[i].to!=fat)
            dfs(e[i].to,now);
        }
    }
    int lca(int x,int y){
        int ans=0;
        if(dep[x]>dep[y]){
            int v=dep[y];
        ans+=(2*(dep[x]-dep[y]));
        while(dep[x]>dep[y]){
        x=fa[x][logg[dep[x]-dep[y]]-1];
        }
        if(x==y)
        return ans;
        for(int k=logg[dep[x]]-1;k>=0;k--){
            if(fa[x][k]!=fa[y][k]){
                x=fa[x][k];
                y=fa[y][k];
            }
        }
        ans+=(3*(v-dep[fa[x][0]]));
        return ans;
        }
        else{
            ans+=(dep[y]-dep[x]);
            int v=dep[x];
        while(dep[x]<dep[y]){
        y=fa[y][logg[dep[y]-dep[x]]-1];
        }
        if(x==y)
        return ans;
        for(int k=logg[dep[x]]-1;k>=0;k--){
            if(fa[x][k]!=fa[y][k]){
                x=fa[x][k];
                y=fa[y][k];
            }
        }
        ans+=(3*(v-dep[fa[x][0]]));
        return ans;
            
        }
    }
    
    void add(int f,int t){
        p++;
        e[p].to=t;
        e[p].ne=head[f];
        head[f]=p;
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n-1;++i){
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        dfs(1,0);
        cout<<md<<endl<<mk<<endl;
        for(int i=1;i<=n;++i)
            logg[i]=logg[i-1]+(1<<logg[i-1]==i);
        for(int i=1;i<=1;++i){
            scanf("%d%d",&x,&y);
            cout<<lca(x,y)<<endl;
        }
        return 0;
    }
    Ac
  • 相关阅读:
    Redis Sentinel:集群Failover解决方案(转载)
    C#获取Windows屏幕尺寸
    C# 获取屏幕的大小 SystemInformation类
    拆分器控件Splitcontainer
    (收藏)《博客园精华集》分类索引(转 )
    Redis内存数据库在Exchange会议室的应用(转)
    【转】开源Math.NET基础数学类库使用(01)综合介绍
    15个nosql数据库
    20个代码生成框架(转)
    nodeJS安装和环境变量的配置
  • 原文地址:https://www.cnblogs.com/For-Miku/p/12210802.html
一二三 - 开发者的网上家园