CF 682C

• 水题，一开始看错题了，orz。 $n<10^5$
• 就是求有多少个点之间的边权值大于深度低的那个点的点权值。
• 每次dfs的时候如果上面的边权值为负了，那么取0再往下传就行。

#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
#include <iostream>
#include <algorithm>
const int maxn = 100007;
int ver[maxn], size[maxn], n;
std::vector<std::pair<int, long long> > lis[maxn];
void getSize(int u, int f){
    size[u] = 1;
    for(auto i : lis[u]){
        int v = i.first;
        if(v == f) continue;
        getSize(v, u);
        size[u] += size[v];
    }
}
int ans = 0;
void dfs(int u, int f, long long val){
    if(val > ver[u]) {
        ans += size[u];
        return;
    }
    for(auto i : lis[u]){
        int v = i.first;
        if(v == f) continue;
        dfs(v, u, std::max(val + i.second, i.second));
    }
}
int main()
{
    int u, val;
    std::cin >> n;
    for(int i = 1; i <= n; i ++){
        std::cin >> ver[i];
    }
    for(int i = 2; i <= n; i ++){
        std::cin >> u >> val;
        lis[i].push_back(std::make_pair(u, val));
        lis[u].push_back(std::make_pair(i, val));
    }
    getSize(1, 1);
    dfs(1, 1, 0);
    std::cout << ans << std::endl;
}