波特尔暗空分类法_老暗锁打不开了怎么办

波特尔暗空分类法_老暗锁打不开了怎么办传说中的暗之连锁被人们称为 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/168621.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • java parrallel for,Java 8 parallel forEach进度指示

    java parrallel for,Java 8 parallel forEach进度指示ForperformancereasonIwouldliketouseaforEachloopofaparallelLambdastreaminordertoprocessaninstanceofaCollectioninJava.AsthisrunsinabackgroundServiceIwouldliketouse…

  • leetcode-152. 乘积最大子数组(动态规划+滚动数组)「建议收藏」

    leetcode-152. 乘积最大子数组(动态规划+滚动数组)「建议收藏」给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。示例 1:输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;int f[2][

  • pycharm添加搜索路径_pycharm系统找不到指定路径

    pycharm添加搜索路径_pycharm系统找不到指定路径为了能让python解释器找到我安装的python包的位置,我把该位置添加到了PYTHONPATH中,结果试了半天,pycharm中的解释器都没能检测到我那个包的存在,而在终端打开python的命令交互模式都是可以获取我在PYTHONPATH中设置的路径的。(气得我一口老血喷出来,哪位大神要是知道这是什么情况,敬请告知呀喵。感激不尽呦^_^)好了,说正事了。pycharm这么气人怎么办呢?闹了半

  • 可变与不可变数据类型

    Python中的数据类型以Python3为例,Python3中有以下几个标准的数据类型划分可变与不可变类型的依据可变数据类型不可变数据类型如何确定是可变还是不可变数据类型根据可变数据类型

  • [ZZ] cbuffer和tbuffer

    [ZZ] cbuffer和tbuffer

  • 后台管理系统登录思路「建议收藏」

    后台管理系统登录思路「建议收藏」一般来说我们不管是做后台管理,还是做普通项目,必不可少的其实就是登录。那么登录又是怎么实现的呢?废话不多说,上代码。首先我们把登录接口封装在一个文件里,如果这个接口有必备的参数,我们就得传参,然后在登录页引入调用。其次就是我们在登录页写登录框信息,这时候就需要接收接口必备的参数,那具体怎么接呢?先在data里设置两个放置参数的空数组。然后在登录信息框中外围prop接收,然后在信息框上v-model获取用户信息。在一个就是当我们填完用户信息的时候做什么逻辑:首先就是调用封装好的登录接口,其次在登录成功

发表回复

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

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