Solution

太菜了,看了雨巨的题解才发自己读错题了 自闭了一天
题目提到如果我们选择i点
i点到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑
那么我们就可以考虑从叶子开始取,因为取非叶子节点永远无法将叶子节点染黑
这样显然就可以用dfs递归从叶子往根染黑
其次,我们发现从叶子节点往上的点可能会因为选取叶子节点而被染黑
但是被染黑不代表就不取,我们可以简单的运用一个等价替换的思想:


考虑图上这种情况,显然权值为3这个点我们一定要取,而它的父亲节点是B权值为1,显然不用取
但是呢,我们可以转换思路,把权值3 - 1赋予给它的父亲节点,取个max即可 a[fa] = max(a[fa], a[u] - 1)
这样的话,我们从下往上,当dp[u] 为 0, 证明下面的节点无法把它包括,需要将这个点染黑
否则, 一直取max往上转移到根节点

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int a[N], dp[N];
int ans;
vector<int> G[N];
void dfs(int u, int par){
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i];
    dfs(v, u);
    a[u] = max(a[u], a[v] - 1);
    dp[u] = max(dp[u], dp[v] - 1);
  }
  if(!dp[u]){
    dp[u] = a[u];
    ans++;
  }
}
int main(){
  int n;
  cin >> n;
  for(int i = 2; i <= n; i++){
    int u;
    cin >> u;
    G[u].push_back(i);
  }
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  ans = 0;
  dfs(1, -1);
  cout << ans << "\n";
  return 0;
}