CodeForces 592D Super M
2024-08-30 16:18:01
先把没用的边去掉,求出包含m个点的最小树。然后求出最小树的直径就可以得到答案了。
#include <cstdio>
#include <cstring>
#include <vector>
#include<cmath>
using namespace std; const int maxn=;
struct Edge
{
int u,v;
int next;
} e[*maxn];
int tot;
int h[maxn];
bool f[maxn],q[maxn];
int head[maxn];
int n,m; int st1,st2;
int len; void add(int a,int b)
{
e[tot].u=a;
e[tot].v=b;
e[tot].next=head[a];
head[a]=tot;
tot++;
} void dfs(int x)
{
f[x]=;
for(int i=head[x]; i!=-; i=e[i].next)
{
if(f[e[i].v]==)
{
dfs(e[i].v);
if(q[e[i].v]==) q[x]=;
}
}
} void Find(int x,int le,int op)
{
f[x]=;
if(op==)
{
if(le>len) len=le,st1=x;
else if(le==len&&x<st1) st1=x;
}
else if(op==)
{
if(le>len) len=le,st2=x;
else if(le==len&&x<st2) st2=x;
} for(int i=head[x]; i!=-; i=e[i].next)
{
if(q[e[i].u]==) continue;
if(q[e[i].v]==) continue;
if(f[e[i].v]==) Find(e[i].v,le+,op);
}
} int main()
{
scanf("%d%d",&n,&m);
memset(f,,sizeof f);
memset(q,,sizeof q);
memset(head,-,sizeof head);
tot=;
for(int i=; i<n; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=; i<=m; i++)
{
int x;
scanf("%d",&x);
q[x]=;
}
int g;
for(int i=; i<=n; i++) if(q[i]==)
{
g=i;
dfs(g);
break;
} st1=st2=0x7FFFFFFF;
memset(f,,sizeof f);
len=;
Find(g,,);
memset(f,,sizeof f);
len=;
Find(st1,,); int ans1=min(st1,st2); int ans2=;
for(int i=; i<tot; i=i+)
{
if(q[e[i].u]==) continue;
if(q[e[i].v]==) continue;
ans2=ans2+;
}
ans2=ans2-len;
printf("%d\n%d\n",ans1,ans2);
return ;
}
最新文章
- JVM学习(4)——全面总结Java的GC算法和回收机制
- c++调用lua环境配置
- fis3-postpackager-loader插件说明
- Android-将RGB彩色图转换为灰度图
- mysql配置详解
- 在hdfs上存取xml文件的实现代码
- linux eclipse
- multi-cursor
- poj 2449 第k短路径
- 在Linux下写一个线程池以及线程池的一些用法和注意点
- Entity Framework 的事务
- switch case加条件语句(非等值) php
- OSGi:生命周期层
- 眼见为实(2):介绍Windows的窗口、消息、子类化和超类化
- Hadoop3.2.0使用详解
- MacOS 10.12 Sierra 安全性与隐私没有任何来源选项解决方法
- 2012年NOIP普及组 摆花
- 群晖搭建webssh
- Mirror--如何TSQL查看镜像状态和镜像相关存储过程
- Alamofire源码导读三:返回的处理逻辑
热门文章
- Data Center Manager Leveraging OpenStack
- 项目中非常有用并且常见的ES6语法
- jmeter的JVM参数设置
- Android(java)学习笔记163:开发一个多界面的应用程序之界面间数据传递
- 版本号对比方案及参考代码(Objective-C,Java,JavaScript)
- 事件冒泡 &; 阻止事件冒泡
- Linux-RedHat7.2 安装.net core2.0
- Qt setWindow setViewPort
- Wow64
- The MySQL server is running with the –secure-file-priv