题目链接https://ac.nowcoder.com/acm/problem/13249

题面

题面

基本思路

  • 由于每个点只能往上更新,所以dfs一遍从叶子结点开始往根结点做选择。
  • 但需要注意如下图所示的情况:当我们dfs回溯到红色的结点时,发现已经选过的结点都无法更新到该结点,那么是直接选择该结点继续往上更新吗?
  • 答案是否定的,因为很明显我们选择权值为10的结点更优,也就是说当某个结点无法被已选择的结点更新时,可能在其子树中存在更优解。
  • 若$a[j]-dist[j,i]>a[i]$,则$j$结点比$i$结点更优,其中$a[i]$表示$i$结点的权值,$dist[j,i]$表示$j$到$i$的路径长度,$j$是$i$的孩子。
  • 可以先dfs一遍获得每个结点的最优解,再dfs一遍求需要操作的最小次数,但显然两次dfs可以合并成一次。
    树

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int n, x;
int k[MAXN];
int dp[MAXN], ans;
struct Edge {
    int v, ne;
} edge[MAXN];
int head[MAXN], tot;
void init() {
    ans = tot = 0;
    memset(dp, 0, sizeof(dp));
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v) {
    edge[tot].v = v;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
void dfs(int id) {
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        dfs(edge[i].v);
        dp[id] = max(dp[id], dp[edge[i].v] - 1);
        k[id] = max(k[id], k[edge[i].v] - 1);
    }
    if(dp[id] == 0) {
        ans++;
        dp[id] = k[id];
    }
}
int main() {
    init();
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) {
        scanf("%d", &x);
        addedge(x, i);
    }
    for(int i = 1; i <= n; i++) scanf("%d", &k[i]);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}
Last modification:April 12th, 2020 at 09:14 pm
如果觉得我的文章对你有用,请随意赞赏