Codeforces 682C

发表于 |

题目

给一棵$N$个节点的树，节点$i$有点权$a_i$。每条边有边权$b_i$。对于节点$u$，如果$u$的子树中存在节点$v$使得$dist(u,v)>a_v$的话，$u$就具有性质$P$。问：最少删去多少个节点，使得剩下的树中没有节点具有性质$P$。其中$dist(u,v):=$$u$到$v$的边权之和。

数据范围

$1\leq N \leq 10^5$

做法

对于$2$个节点$(u,v)$（$u$是$v$的祖先），如果$dist(u,v)>a_v$，必须删去以u到v的某个点为根的子树。为了删去最少，显然删去以$v$为根的子树。

$dist(u,v)=dist(1,v)−dist(1,u)$，所以我们处理出根到每个节点的距离即可。但是枚举任意2个点$uv$复杂度太高，我们可以在$dfs$的时候，维护一个min_dist(从根节点到当前节点距离的最小值)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 5;
struct edge {int to; ll cost;};
int N;
ll a[MAX_N];
vector<edge> G[MAX_N];
int sz[MAX_N];
ll minDist[MAX_N];
int ans;
void AddEdge(int a, int b, ll c)
{
  G[a].push_back((edge){b, c});
  G[b].push_back((edge){a, c});
}
void dfs(int v, int p, ll dist, bool exist)
{
  sz[v] = 1;
  minDist[v] = min(minDist[p], dist);
  bool del = dist - minDist[p] > a[v];
  for (int i = 0; i < (int)G[v].size(); ++i) {
    edge &e = G[v][i];
    if (e.to != p) {
      dfs(e.to, v, dist + e.cost, exist && !del);
      sz[v] += sz[e.to];
    }
  }
  if (exist && del) ans += sz[v];
}
int main()
{
  cin >> N;
  for (int i = 0; i < N; ++i) scanf("%lld", a + i);
  for (int i = 0; i < N - 1; ++i) {
    int to; ll c; scanf("%d%lld", &to, &c);
    AddEdge(--to, i + 1, c);
  }
  a[0] = INT_MAX;
  minDist[0] = 0;
  dfs(0, 0, 0, 1);
  printf("%d\n", ans);
  return 0;
}