先把没用的边去掉,求出包含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 ;
}

最新文章

  1. JVM学习(4)——全面总结Java的GC算法和回收机制
  2. c++调用lua环境配置
  3. fis3-postpackager-loader插件说明
  4. Android-将RGB彩色图转换为灰度图
  5. mysql配置详解
  6. 在hdfs上存取xml文件的实现代码
  7. linux eclipse
  8. multi-cursor
  9. poj 2449 第k短路径
  10. 在Linux下写一个线程池以及线程池的一些用法和注意点
  11. Entity Framework 的事务
  12. switch case加条件语句(非等值) php
  13. OSGi:生命周期层
  14. 眼见为实(2):介绍Windows的窗口、消息、子类化和超类化
  15. Hadoop3.2.0使用详解
  16. MacOS 10.12 Sierra 安全性与隐私没有任何来源选项解决方法
  17. 2012年NOIP普及组 摆花
  18. 群晖搭建webssh
  19. Mirror--如何TSQL查看镜像状态和镜像相关存储过程
  20. Alamofire源码导读三:返回的处理逻辑

热门文章

  1. Data Center Manager Leveraging OpenStack
  2. 项目中非常有用并且常见的ES6语法
  3. jmeter的JVM参数设置
  4. Android(java)学习笔记163:开发一个多界面的应用程序之界面间数据传递
  5. 版本号对比方案及参考代码(Objective-C,Java,JavaScript)
  6. 事件冒泡 &amp; 阻止事件冒泡
  7. Linux-RedHat7.2 安装.net core2.0
  8. Qt setWindow setViewPort
  9. Wow64
  10. The MySQL server is running with the –secure-file-priv