2023年3月8日 https://codeforces.com/problemset/problem/337/D
输入 n m(1≤m≤n≤1e5) d(0≤d≤n-1) 表示一棵 n 个节点的树,其中 m 个节点有怪物,
这些怪物是由一个传送门生成的,传送门与任意怪物的距离不超过 d。
然后输入 m 个互不相同的数,表示怪物所在节点编号(从 1 开始)。
然后输入 n-1 行,每行两个节点编号,表示树的边。
输出可能存在传送门的节点的个数。注意传送门只有一个。
inputCopy
6 2 3
1 2
1 5
2 3
3 4
4 5
5 6
outputCopy
3
1.v -> w 如果v往下走的最长距离不经过w
那么w往上走的最长距离为max(v往下走的最长距离,v往上走的最长距离) + 1;
2.v -> w 如果v往下走的最长距离经过w
那么w往上走的最长距离为max(v往下走的次长距离,v往上走的最长距离) + 1;
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 2 * N;
int n, m, k;
int e[M], ne[M], h[N], idx;
bool st[N];
int p[N];
int up[N], down1[N], down2[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u, int fa)
{
if(st[u]) down1[u] = down2[u] = 0;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
int d = dfs(j, u) + 1;
if(st[j])
{
st[u] = true;
if(d >= down1[u]) down2[u] = down1[u], down1[u] = d, p[u] = j;
else if(d > down2[u]) down2[u] = d;
}
}
return down1[u];
}
void dfs1(int u, int fa){
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(j == fa) continue;
if(p[u] == j){
up[j] = max(down2[u], up[u]) + 1;
}
else up[j] = max(up[u], down1[u]) + 1;
dfs1(j, u);
}
}
int main ()
{
cin >> n >> m >> k;
memset(up, -0x3f, sizeof up);
memset(down1, -0x3f, sizeof down1);
memset(down2, -0x3f, sizeof down2);
for(int i = 1; i <= m; i ++)
{
int x;
cin >> x;
st[x] = true;
}
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; i ++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
int _ = dfs(1, -1);
dfs1(1, -1);
int res = 0;
for(int i = 1; i <= n; i ++){
int d = max(up[i], down1[i]);
if(d <= k) res ++;
}
cout << res << endl;
return 0;
}