526互联

abc309e <dfs>

发布时间 2023-07-09 12:09:01作者: O2iginal

E - Family and Insurance

// https://atcoder.jp/contests/abc309/tasks/abc309_e
// <dfs>
// 关键在于意识到, 每个结点保留最大后代数即可 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
vector<int> g[N];
int cnt[N], ans;

void dfs(int u)
{
    if(cnt[u]) ans ++;
    for (auto &v: g[u])
    {
        cnt[v] = max(cnt[v], cnt[u]-1);  // 仅保留最大值
        dfs(v);
    }
}

void solv()
{
    int n, m;
    cin >> n >> m;
    for (int i = 2; i <= n; i ++)
    {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    int x, y;
    while(m --)
    {
        cin >> x >> y;
        cnt[x] = max(cnt[x], y + 1);  // 这里+1, 以方便用0来标记没有insurance
    }
    dfs(1);
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}