BZOJ 3631 松鼠的新家-程序员宅基地

技术标签: LCA  

题意:
有一棵树,n个节点,从a1出发->a2->a3->…->an,(a为一个排列),每经过一个节点时,该节点加一,问最终每个节点的值


思路:
类似差分,lca(u,v)+1,u-1,v-1,从上往下统计答案就可以了

u+1,v+1,lca(u,v)-1,fa[lca[u,v]]-1,从下往上扫描


#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=3e5+100;
const int DEG=20;
struct Edge{
    int to,next;
}e[N*2];
int a[N],ans[N],tot,head[N];

void init(){
    tot=0;
    memset(head,-1,sizeof(head));
}

void addedge(int from,int to){
    e[tot]=(Edge){to,head[from]};
    head[from]=tot++;
}

int fa[N][DEG];
int deg[N],degree[N];

void bfs(int root){
    queue<int>Q;
    deg[root]=0;
    fa[root][0]=0;
    Q.push(root);
    while(!Q.empty()){
        int tmp=Q.front();
        Q.pop();
        for(int i=1;i<DEG;i++)
            fa[tmp][i]=fa[fa[tmp][i-1]][i-1];
        for(int i=head[tmp];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(v==fa[tmp][0])   continue;
            degree[tmp]++;
            deg[v]=deg[tmp]+1;
            fa[v][0]=tmp;
            Q.push(v);
        }
    }
}

int LCA(int u,int v){
    if(deg[u]>deg[v])   swap(u,v);
    int tu=u,tv=v;
    for(int det=deg[v]-deg[u],i=0;det;det>>=1,i++)
        if(det&1)
            tv=fa[tv][i];
    if(tu==tv)  return tu;
    for(int i=DEG-1;i>=0;i--){
        if(fa[tu][i]==fa[tv][i])
            continue;
        tu=fa[tu][i],tv=fa[tv][i];
    }
    return fa[tu][0];
}

void get_ans(int n){
    queue<int>Q;
    for(int i=1;i<=n;i++)
        if(degree[i]==0)
            Q.push(i);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(v!=fa[u][0]) continue;
            degree[v]--,ans[v]+=ans[u];
            if(degree[v]==0)
                Q.push(v);
        }
    }
}

int main(){
    int n,u,v;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    init();
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        addedge(u,v),addedge(v,u);
    }
    bfs(1);
    for(int i=2;i<=n;i++){
        int lca=LCA(a[i],a[i-1]);
        ans[ a[i-1] ]++,ans[ fa[a[i]][0] ]++;
        ans[ fa[lca][0] ]--,ans[ lca ]--;
    }
    get_ans(n);
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/acm_fighting/article/details/53018029

智能推荐

Zillow“炒房”失败,算法神话破灭了吗?-程序员宅基地

文章浏览阅读1.3k次。新冠时代,裁员、失业在全球范围内都是高频事件,我们似乎早就已经习惯了各种黑天鹅消息。不过美国地产平台Zillow在年底彻底关停iBuying业务,并将该业务约2000名员工全部裁掉的消息,...

navicat创建表不显示问题解决-程序员宅基地

文章浏览阅读5.1k次。在创建数据表时,我们会发现navicat创建表不显示问题?以下有三种解决方法!

SSH服务器拒绝了密码。请再试一次 问题解决_ssh拒绝了密码,请再试一次-程序员宅基地

文章浏览阅读1.1k次。SSH服务器拒绝了密码。请再试一次1.问题 SSH服务器拒绝了密码。请再试一次2.查看配置vim /etc/ssh/sshd_config找到Authentication# Authentication:#LoginGraceTime 2m#PermitRootLogin yes#StrictModes yes把配置改成# Authentication:LoginGraceTime 2mPermitRootLogin yesStrictModes yes重启s_ssh拒绝了密码,请再试一次

黑马IOS基础课程的学习笔记 C语言基础_黑马朴乾-程序员宅基地

文章浏览阅读576次。昨天弄了一天虚拟机是装上了 不过 这速度 装Xcode也死活装不上。。无爱了。。在MAC系统中的终端操作指令cc -c文件名.c // 要有空格编译成功会生成一个.o的目标文件链接 指令 CC 文件名.o 要有空格 貌似能多个文件一起链接的样子。 其实就是把我们的.o目标文件跟系统自带的库函数合并在一起,生成一个可_黑马朴乾

创建ICC2/ICC所需要的tech file(.tf)_icc 没有.tf文件怎么办-程序员宅基地

文章浏览阅读3.7k次,点赞2次,收藏7次。最近摸索了一下ICC2创建tech file的过程。首先,我手上有什么?没错,我什么都没有,只有stdcell的Layout.1. 通过icfb dump出tech.lef文件。这个过程中,需要选择一个technology library, 而technolgy library可以选择项目中的tech lib。一般在创建tech lib的时候,会关联virtuoso的Tech file.因此,选择这个library,就相当于关联了一个tech file (virtuoso版本的)。然后export l_icc 没有.tf文件怎么办

react Native 执行 run-android报错Failed to launch emulator. Reason: Emulator exited before boot._error failed to launch emulator. reason: emulator -程序员宅基地

文章浏览阅读1.3w次。react Native 执行 run-android 错误,报错如图报错信息:未能启动模拟器。原因:模拟器在启动前退出。原因:x86镜像的模拟器启动不了,因为HAMX没有安装。Android SDK已经集成了HAMX这个软件,我们需要做的就是找到他,然后安装就可以了。文件路径:存放于你的SDK下面的D:\Program Files\Android\AndroidSDK\(自己指定的SD..._error failed to launch emulator. reason: emulator exited before boot..

随便推点

nagios报错NRPE: Command 'check_heartbeat' not defined_nrpe: command 'check_cberp_mongodb' not defined-程序员宅基地

文章浏览阅读2.4k次。最近在做heartbeat监控的时候,在nagios服务器端报警提示:NRPE: Command 'check_heartbeat' not defined但是在nagios客户端/usr/local/nagios/libexec/check_nrpe -H 192.168.3.211 -c check_heartbeat都能够正常执行,查了很多资料主要有以下几种情况:1.nagios客户_nrpe: command 'check_cberp_mongodb' not defined

nth-child是以1开头_&:nth-child 从1开始-程序员宅基地

文章浏览阅读284次。一不注意,就要掉坑里面.外国人的东西,坑太多了._&:nth-child 从1开始

【HRBUST - 1996】数学等式 (HASH 或 二分)_现在给出三个数字a,b和c,你可以在保证a+b不变的情况下对两数进行调整,设调整以后-程序员宅基地

文章浏览阅读360次。题干:又到了数学题的时刻了,给出三个数组A,B,C,然后再给出一个数X,现在我想知道是否能找到三个数满足等式A[i]+B[j]+C[k]=X,你能帮助我么??Input本题有多组数据,每组数据第一行输入三个数n,m,h,分别表示数组A,B,C内的的元素个数(0<n,m,h<=500)接下来三行分别输入数组A,B,C的元素接下来输入一个数Q,表示Q次询问(1&l..._现在给出三个数字a,b和c,你可以在保证a+b不变的情况下对两数进行调整,设调整以后

数据可视化基本套路总结-程序员宅基地

文章浏览阅读2k次,点赞3次,收藏13次。真依然很拉风,简书《数据可视化》专栏维护者,里面有很多优秀的文章,本文便是其中一篇。文章总结了多种数据可视化图形,并简要介绍了各种图形的作用,能为科研工作者在数据可视化阶段提供新的思路,..._计算机设计大赛经验分享,数据可视化

鸿蒙智联生态产品《接入智慧生活App开发指导》(官方更新版)_万和热水器如何加入鸿蒙智联-程序员宅基地

文章浏览阅读1.3k次。在HarmonyOS Connect生态产品应用开发过程中,很多开发者对于如何接入智慧生活App还存在一些疑问,如:如何选择合适的开发方式、如何进行H5开发与调测等。为了更好地帮助开发者,官方文档特意整理出“接入智慧生活App”专题。跟紧小编的步伐,赶紧来看看本次文档更新内容~文档中心-接入智慧生活App的开发指导:文档中心智慧生活App作为华为全场景智慧体验的重要入口,可以实现华为自研设备与生态伙伴设备的统一管理。图1 智慧生活App伙伴可以通过开发H5..._万和热水器如何加入鸿蒙智联

Typescript error :Property mozRequestFullScreen' does not exist on type 'HTMLElement'_属性“mozrequestfullscreen”在类型“htmlelement”上不存在。你是否指的-程序员宅基地

文章浏览阅读1.2k次。当我一开始在做全屏功能的时候,遇到了以下这个问题:Typescript error :Property mozRequestFullScreen' does not exist on type 'HTMLElement'.其他类似问题:property ‘xxx’ does not exist on type ‘yyy’解决:声明用let de : any;..._属性“mozrequestfullscreen”在类型“htmlelement”上不存在。你是否指的是“req

推荐文章

热门文章

相关标签