[CF592D] Super M - 树的直径
Description
有一个有 n 个节点的树,其中有 m 个点被标记。现在从任意点开始,去遍历这 m 个点,问你遍历这 m个点的最少路程(边的权值为1)。
Solution
答案显然是这个标记点构成的虚树大小减去虚树直径
当然我们不需要真的建虚树,从一个标记点开始 DFS,考察子树内是否有标记点即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
const int N = 1e6 + 5;
vector<int> g[N];
int dep[N], siz[N], tag[N];
void dfs(int p, int from)
{
siz[p] = 0;
for (int q : g[p])
{
if (q == from)
continue;
dep[q] = dep[p] + 1;
dfs(q, p);
siz[p] += siz[q];
}
if (tag[p] || siz[p])
++siz[p];
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i < n; i++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
int s = 1e9;
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
s = min(s, x);
tag[x] = 1;
}
if (m == 1)
{
cout << s << endl
<< 0 << endl;
}
else
{
dep[s] = 1;
dfs(s, 0);
for (int i = 1; i <= n; i++)
dep[i] *= tag[i];
int a = 0;
for (int i = 1; i <= n; i++)
if (dep[i] > dep[a])
a = i;
dep[a] = 1;
dfs(a, 0);
for (int i = 1; i <= n; i++)
dep[i] *= tag[i];
int len = *max_element(dep + 1, dep + n + 1);
int b = 0;
for (int i = 1; i <= n; i++)
if (dep[i] > dep[b])
b = i;
cout << min(a, b) << endl
<< 2 * (siz[a] - 1) - len + 1 << endl;
}
}