波特尔暗空分类法_光辉战机和歼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)


相关推荐

  • ERP和MES、QAS以及APS在制造企业信息化的了解

    ERP和MES、QAS以及APS在制造企业信息化的了解ERP系统企业ERP系统标准的定义来自其英文原意,即企业资源规划(EnterpiseResourcePlanning)。企业ERP系统是一个对企业资源进行有效共享与利用的系统,通过信息系统对信息进行充分整理、有效传递、使企业的资源在购、存、产、销、人、财、物等各个方面能够得到合理地配置与利用,从而实现企业经营效率地提高。从本质上讲,企业ERP系统时一套信息系统,是一种工具。系统设计中可集成某些管理思想与内容,可帮助企业提升管理水平。另外一种说法认为企业ERP系统是将企业所有资源进行整合集成管理,简单

  • YUM常用命令介绍

    YUM常用命令介绍

  • vue中显示静态图片怎么引用

    vue中显示静态图片怎么引用

  • CNN卷积神经网络原理讲解+图片识别应用(附源码)[通俗易懂]

    CNN卷积神经网络原理讲解+图片识别应用(附源码)[通俗易懂]一、机器如何识图先给大家出个脑筋急转弯:在白纸上画出一个大熊猫,一共需要几种颜色的画笔?——大家应该都知道,只需要一种黑色的画笔,只需要将大熊猫黑色的地方涂上黑色,一个大熊猫的图像就可以展现出来。我们画大熊猫的方式,其实和妈妈们的十字绣很接近——在给定的格子里,绣上不同的颜色,最后就可以展现出一幅特定的“图片”。而机器识图的方式正好和绣十字绣的方式相反,现在有了一幅图片,机器通过识别图片中…

  • hdu 5077 NAND(暴力打表)

    hdu 5077 NAND(暴力打表)

  • 史上最详细的Hadoop环境搭建

    史上最详细的Hadoop环境搭建GitChat作者:鸣宇淳原文:史上最详细的Hadoop环境搭建关注公众号:GitChat技术杂谈,一本正经的讲技术【不要错过文末活动哦】前言Hadoop在大数据技术体系中的地位至关重要,Hadoop是大数据技术的基础,对Hadoop基础知识的掌握的扎实程度,会决定在大数据技术道路上走多远。这是一篇入门文章,Hadoop的学习方法很多,网上也有很多学习路线图。本文的思路是:以安装部署A

发表回复

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

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