题意：给定一颗n个结点的树，树上有m个结点有队伍，求存不存在一个点s，到所有m个队伍所在结点的距离相等，如果存在输出可能一个的s。
分析：假设存在s，那么可以改变树的顺序，使得s是所有队伍结点的祖先，此时s的所有祖先都是满足的s，令所有满足条件的s中里队伍结点最近的s为ms。dfs可以求得队伍结点中的直径，直径端点为st，ed。如果直径是奇数，肯定不存在，因为已知不存在与st，ed距离相等的点。如果直径是偶数，令直径的中点为c，因为假设s存在，所以st，ed的中点一定是所有点的中点，而且此时c一定是ms，此时验证c是否满足条件即可。dfs验证c到所有队伍结点的距离是否相等，如果满足条件，输出c。
需要注意的是，当只有一个队伍节点时，st=ed，两遍dfs找直径时需要把直径长度置为0，否则无法找到ed。
代码：
#include <bits/stdc++.h> #define mp make_pair #define debug(x) cout << #x << ": " << x << endl #define pb push_back typedef long long LL; const int maxn = 3e5 + 10; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; using namespace std; int n, m, len, u, v, f[maxn], path[maxn], st, ed, dis[maxn], c; vector<int> g[maxn]; void dfs(int now, int pre,int steps) { if (f[now]) { if (steps >= len) { st = now; len = steps; } } for (int i = 0; i < g[now].size(); ++i) { int to = g[now][i]; if (to == pre) continue; dfs(to, now, steps + 1); } } void _dfs(int now, int pre, int steps) { if (f[now]) dis[now] = steps; for (int i = 0; i < g[now].size(); ++i) { int to = g[now][i]; if (to == pre) continue; _dfs(to, now, steps + 1); } } void __dfs(int now, int pre, int steps) { if (f[now]) { if (steps >= len) { ed = now; len = steps; } } for (int i = 0; i < g[now].size(); ++i) { int to = g[now][i]; if (to == pre) continue; path[to] = now; __dfs(to, now, steps + 1); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; st = ed = len = 0; for (int i = 1; i < n; ++i) { cin >> u >> v; g[u].pb(v); g[v].pb(u); } for (int i = 0; i < m; ++i) { cin >> u; f[u] = 1; } dfs(1, 0, 0); len = 0; __dfs(st, 0, 0); if (len & 1) { cout << "NO\n"; } else { int temp = ed; int cnt = 0; while (cnt != len / 2) { temp = path[temp]; ++cnt; } c = temp; _dfs(c,0,0); int x = -1; for (int i = 1; i <= n; ++i) { if (f[i]) { if (x == -1) x = dis[i]; else if (dis[i] != x) { cout << "NO\n"; exit(0); } } } cout << "YES\n" << c; } }
codeforeces gym102411 Equidistant（图论+乱搞）
原文：https://www.cnblogs.com/smallhester/p/11815645.html