J题： Free https://blog.csdn.net/canxuezhinuanyang/article/details/97671247
题意：给你n个城市，m条道路，经过每一条要花费这条路的代价，现给你k个机会，使得最多k条路的代价为0，问从起点s到终点t花费的最少代价
思路：据说是分层图最短路经典裸题 ：https://www.cnblogs.com/wizarderror/p/11262719.html
但是考虑两个相距最远的关键点，假设他们的距离为d，那么答案肯定为(d+1)/2。
如果有一点到中心点的距离超过了(d+1)/2 ，那么这个点会成为最远关键点对中的一个。矛盾。
所以题目就变成了如何求最远的两个关键点的距离。
考虑如何求树的直径，首先取一个根节点通过bfs找到离他最远的叶子节点p，然后将p当做根节点再跑一遍BFS
求出离这个点最远的叶子节点q,那么从p到q的这条路径就是树的直径。
那么两个最远的关键点的距离就相当求出将关键点当成叶子节点的一棵树的直径，我们取一个点当根节点然后
BFS找到离他最远的关键点p 以这个关键点p为根节点再跑一遍BFS求出离这个关键点最远的关键点q，则p到q的路
径就是我们要找关键点最远距离d 然后 ans=(d+1)/2更新答案。
#include<bits/stdc++.h> using namespace std; const int maxn=100005; int n,k; vector<int>g[maxn]; int vis[maxn],flag[maxn],dis[maxn]; int bfs(int x) { int ans; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); queue<int>q; q.push(x); vis[x]=1; dis[x]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(!vis[v]) { dis[v]=dis[u]+1; if(flag[v])ans=v; vis[v]=1; q.push(v); } } } return ans; } int main() { cin>>n>>k; int u,v; for(int i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } int y; for(int i=1;i<=k;i++) { scanf("%d",&y); flag[y]=1; } int s,t; s=bfs(1); t=bfs(s); cout<<(dis[t]+1)/2<<endl; return 0; }