这题不难,当时想出来了,可是却写不出来~~

现在慢慢写回来,也写得好挫~

可以知道,被攻击的城市必定可以组成一棵树,然后,传送到的点必定也是城市之一。如果出发后回到原点,则需要2E,E是树的边数,则2E-D就是答案,D是树中直径。

我写得好锉~

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define LL long long
using namespace std; const int MAX=123460; struct Edge{
int u,v,next;
}edge[MAX*2]; int head[MAX],dis[MAX];
int n,m,tot;
bool chose[MAX];
int pre[MAX],point[MAX],deg[MAX];
int dis1[MAX],node1[MAX],dis2[MAX],node2[MAX];
bool vis[MAX]; void addedge(int u,int v){
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
} int BFS(int rt,int counts){
queue<int>que;
que.push(rt);
vis[rt]=true;
int u,v;
while(!que.empty()&&counts){
u=que.front();
que.pop();
vis[u]=true;
if(chose[u]) counts--;
for(int e=head[u];e!=-1;e=edge[e].next){
v=edge[e].v;
if(vis[v]) continue;
que.push(v);
pre[v]=u;
}
}
memset(vis,false,sizeof(vis));
while(!que.empty()) que.pop(); for(int i=1;i<=m;i++) que.push(point[i]);
while(!que.empty()){
u=que.front();
que.pop();
v=pre[u];
if(v!=-1){
if(!vis[v]){
que.push(v);
chose[v]=false;
}
vis[v]=true;
}
} while(!que.empty()) que.pop();
memset(vis,false,sizeof(vis));
for(int i=1;i<=m;i++) if(chose[point[i]]) que.push(point[i]);
memset(deg,0,sizeof(deg));
int ans=0;
while(!que.empty()){
u=que.front();
vis[u]=true;
que.pop();
v=pre[u];
if(v!=-1){
ans++;
if(!vis[v])
que.push(v);
deg[v]++;
vis[v]=true;
}
} while(!que.empty()) que.pop();
for(int i=1;i<=m;i++) if(chose[point[i]]) que.push(point[i]);
while(!que.empty()){
u=que.front();
dis[dis1[u]]=dis[dis1[u]]==0?min(node1[u],u):min(min(node1[u],u),dis[dis1[u]]);
dis[dis1[u]+dis2[u]]=dis[dis1[u]+dis2[u]]==0?min(node1[u],node2[u]):min(min(node1[u],node2[u]),dis[dis1[u]+dis2[u]]);
que.pop();
v=pre[u];
if(v!=-1){
deg[v]--;
if(!deg[v]) que.push(v);
dis1[u]+=1;
if(dis1[u]>dis1[v]){
dis2[v]=dis1[v],node2[v]=node1[v];
dis1[v]=dis1[u],node1[v]=node1[u];
}
else if(dis1[u]==dis1[v]){
if(node1[u]<node1[v]){
dis2[v]=dis1[v],node2[v]=node1[v];
node1[v]=node1[u];
}
else{
if(dis1[u]>dis2[v]){
dis2[v]=dis1[u],node2[v]=node1[u];
}
else if(dis1[u]==dis2[v]){
if(node1[u]<node2[v]){
node2[v]=node1[u];
}
}
}
}
else{
if(dis1[u]>dis2[v]){
dis2[v]=dis1[u],node2[v]=node1[u];
}
else if(dis1[u]==dis2[v]){
if(node1[u]<node2[v]){
node2[v]=node1[u];
}
}
} }
}
/// cout<<ans<<endl;
/// printf("%d\n",node1[rt]);
for(int i=n;i>=1;i--){
if(dis[i]>0){
printf("%d\n",dis[i]);
return ans*2-i;
}
}
printf("%d\n",point[1]);
return ans; } int main(){
int u,v;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++){
head[i]=-1,chose[i]=false,pre[i]=-1;
dis1[i]=dis2[i]=0,node1[i]=node2[i]=i;
vis[i]=false; dis[i]=0;
}
tot=0;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
for(int i=1;i<=m;i++){
scanf("%d",&u);
point[i]=u;
chose[u]=true;
}
printf("%d\n",BFS(u,m)); }
return 0;
}

  

最新文章

  1. 【手记】WebBrowser响应页面中的blank开新窗口及window.close关闭本窗体
  2. unordered容器
  3. Python 调用百度翻译API
  4. JSP中的EL
  5. 8、网页制作Dreamweaver(jQuery基础:安装、语法)
  6. jQuery两句话实现HTML转义与反转义
  7. jupyterhub
  8. html+css--水平居中总结-不定宽块状元素方法(三)
  9. Remote Direct Memory Access (RDMA)
  10. js框架页跳转
  11. hdu2089(数位dp)
  12. 使用QT 4.8.6 + Cmake 3.0.0 编译 最新版本OpenCv3.0.0
  13. 怎样让pl sql developer 界面视图复位
  14. javascript 按位或(|),无符号右移(&gt;&gt;&gt;)运算,组合技巧来实现————密码强度提示,四种情况??
  15. 产品经理学Python:参数传递方式
  16. SpringCloud(8)微服务监控Spring Boot Admin
  17. JavaScript 特效之四大家族(offset/scroll/client/event)
  18. css上传图片中等待不可点击效果
  19. Git .gitignore文件的使用
  20. RDLC 主从报表筛选

热门文章

  1. phpStorm更新后配置svn无法使用
  2. javascript中window,document,body的解释
  3. 如何获取select控件的option值和Value?
  4. scala的枚举
  5. 如何扒取一个网站的HTML和CSS源码
  6. Android 升级安装APK兼容Android7.0,解决FileUriExposedException
  7. JS高级——浏览器的线程
  8. CAD读取属性块
  9. 前端自动化构建工具gulp使用
  10. 数组题汇总(python3)