波特尔暗空分类法_光辉战机和歼10c对比

波特尔暗空分类法_光辉战机和歼10c对比传说中的暗之连锁被人们称为 Dark。Dark 是人类内心的黑暗的产物,古今中外的勇者们都试图打倒它。经过研究,你发现 Dark 呈现无向图的结构,图中有 N 个节点和两类边,一类边被称为主要边,而另一类被称为附加边。Dark 有 N–1 条主要边,并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。另外,Dark 还有 M 条附加边。你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态,你只能选择一条主要边切断。一旦你切断了一条主要边,Dark

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

传说中的暗之连锁被人们称为 Dark。

Dark 是人类内心的黑暗的产物,古今中外的勇者们都试图打倒它。

经过研究,你发现 Dark 呈现无向图的结构,图中有 N 个节点和两类边,一类边被称为主要边,而另一类被称为附加边。

Dark 有 N–1 条主要边,并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。

另外,Dark 还有 M 条附加边。

你的任务是把 Dark 斩为不连通的两部分。

一开始 Dark 的附加边都处于无敌状态,你只能选择一条主要边切断。

一旦你切断了一条主要边,Dark 就会进入防御模式,主要边会变为无敌的而附加边可以被切断。

但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道,一共有多少种方案可以击败 Dark。

注意,就算你第一步切断主要边之后就已经把 Dark 斩为两截,你也需要切断一条附加边才算击败了 Dark。

输入格式
第一行包含两个整数 N 和 M。

之后 N–1 行,每行包括两个整数 A 和 B,表示 A 和 B 之间有一条主要边。

之后 M 行以同样的格式给出附加边。

输出格式
输出一个整数表示答案。

数据范围
N≤100000,M≤200000,数据保证答案不超过231−1

输入样例:
4 1
1 2
2 3
1 4
3 4
输出样例:
3

题解
最近公共祖先标记每条边的数量

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 4e5 + 10;
const int maxbit = 20;
int f[N][maxbit],depth[N];
int dif[N];
struct Edge{ 
   
    int v,next;
}edge[M];
int head[N],cnt;
int n,m,sum[N];

void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int lca(int a,int b){ 
   
    if(depth[a] < depth[b])swap(a,b);
    for(int i = maxbit - 1;i >= 0;i --){ 
   
        if(depth[f[a][i]] >= depth[b])a = f[a][i];
    }
    if(a == b)return a;
    for(int i = maxbit - 1;i >= 0;i --){ 
   
        if(f[a][i] != f[b][i]){ 
   
            a = f[a][i];
            b = f[b][i];
        }
    }
    return f[a][0];
}
void dfs(int u,int fa,int d){ 
   
    f[u][0] = fa;
    depth[u] = d;
    for(int i = 1;i < maxbit;i ++)f[u][i] = f[f[u][i - 1]][i - 1];
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int v = edge[i].v;
        if(v == fa)continue;
        dfs(v,u,d + 1);
    }
}
int dfs1(int u,int fa){ 
   
    int ans = 0;
    sum[u] += dif[u];
    for(int i = head[u];~i;i =edge[i].next){ 
   
        int v = edge[i].v;
        if(v == fa)continue;
        ans += dfs1(v,u);
        sum[u] += sum[v];
    }
    if(u != 1){ 
   
        if(sum[u] == 0) ans += m;
        else if(sum[u] == 1)ans += 1;
    }
    return ans;
}
int main(){ 
   
    cin>>n>>m;
    int x,y,w;
    memset(head,-1,sizeof head);
    for(int i = 0;i < n - 1;i ++){ 
   
        cin>>x>>y;
        add(x,y),add(y,x);
    }
    dfs(1,0,1);
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y;
        dif[x] += 1;
        dif[y] += 1;
        dif[lca(x,y)] -= 2;
    }
    cout<<dfs1(1,-1)<<endl;
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169111.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 激光测距芯片VL53L0X的使用与代码

    激光测距芯片VL53L0X的使用与代码一、介绍1、原理采用940nm垂直腔面发射激光器(Vertical-CavitySurface-EmittingLaser,简称VCSEL)发射出激光,激光碰到障碍物后反射回来被VL53L0X接收到,测量激光在空气中的传播时间,进而得到距离。VCSEL相关知识2、参数超小体积:4.4×2.4×1.0mm最大测距:2m发射的激光对眼镜安全,且完全不可见。工作电压:2.6to3.5V通信方式:IIC,400KHz,设备地址0x52,最低位是读…

  • 安全帽识别系统-智慧工地的守夜人

    安全帽识别系统-智慧工地的守夜人在企业作业和工地施工过程中,安全永远高于一切。大家都知道,在进入工作现场是必须佩戴安全帽的,传统的检查方法主要靠安检人员一个一个的检查,这种方法耗时费力却无法保证效果。深圳强美推出鹰眸安全帽识别系统之后,这项工作就与人工智能紧密相联,跨入了高科技时代。安全帽识别系统能够实时对未佩戴安全帽的行为发出警告,及时提醒监理人员处理,为作业人员筑起一道人工智能的安全防火墙。鹰眸安全帽识别系统面世之后,在业…

  • IDEA使用JDBC连接MySQL数据库详细教程「建议收藏」

    IDEA使用JDBC连接MySQL数据库详细教程「建议收藏」首先需要保证你已经成功安装mysql接下来下载连接MySQL数据库的驱动使用JDBC连接MySQL数据库的驱动为Connentor/J,这里以最新版本的8.0为例解压zip文件,随便解压到一个地方就好,当然作为程序员,需要有好习惯的创建java项目,导入mysql-connector-java-8.0.13.jar包下面再来看下导入jar的步骤写代码//导入包importja…

  • YUM源仓库配置_开源仓库

    YUM源仓库配置_开源仓库YUM源仓库配置YUM源仓库配置YUM简介软件仓库的提供方式RPM软件包的来源以ftp方式构建YUM仓库1.在服务器上安装ftp2.命名服务器地址3.查看挂载4.进行匿名登录设置5.在一个客户机上登录安装ftp6.查看文件上传是否成功7.在服务器上查看yum源文件8.移动所有源文件到backup中,并创建新的目录源文件f.repo9.查看配置文件10.移动所有挂载目录下的文件到ftp下11.清除所有缓存,建立缓存12.安装ftp进行测试,ftp方式的yum仓库源是否可行YUM常用命令1.查询软件包2.查询

    2022年10月28日
  • Java:JVM垃圾回收机制[通俗易懂]

    Java:JVM垃圾回收机制[通俗易懂]JVM垃圾回收机制提到Java垃圾回收机制就不得不提到一个方法:system.gc()用于调用垃圾收集器,在调用时垃圾收集器将运行以回收未使用的内存空间,它将尝试释放被丢弃对象所占用的空间。作为程序员有必要了解gc方法,这也是在面试中经常会被问及的问题:我们从三个方面来理解gc:1.JVM如何确定哪些空间能被回收?2.JVM会在什么时候进行垃圾清除的动作?3.JVM如何清除垃圾的?1.JVM如…

  • javascript中条件运算符判断成年_c语言中条件运算符

    javascript中条件运算符判断成年_c语言中条件运算符条件运算符也称三木运算符,三元运算符;例题:// 是否年满18岁 varnum=+prompt(‘请输入年龄’); num>=18&&num>0?alert(‘你已成年’):alert(‘你未满18岁’); // 从两个数中找最大值 varnum1=+prompt(‘输入第一个数字’); varnum2=+prompt(‘输入…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号