本文共 1476 字，大约阅读时间需要 4 分钟。

题意： 来源（洛谷翻译

代码:

#pragma GCC optimize(3 , "Ofast" , "inline")#include
   
    using namespace std;#define int long long#define endl '\n'const int maxn = 6e5+10;int mod=1e9+7;int n;int a[maxn];vector
    
     
       > edge[maxn];int dep[maxn],dis[maxn];int f[maxn][25];void dfs(int x,int w,int fa){
       f[x][0]=fa;    dep[x]=dep[x]+1;    dis[x]=dis[fa]+w;    for(int i=1;i<=20;i++){
           f[x][i]=f[f[x][i-1]][i-1];    }    for(auto i:edge[x]){
           dfs(i.first,i.second,x);    }}int b[maxn];void sol(int now){
       int x=now;    for(int i=20;i>=0;i--){
           if(f[x][i]&&dis[now]-dis[f[x][i]]<=a[now]){
               x=f[x][i];        }    }    b[f[x][0]]--;    b[f[now][0]]++;}void DFS(int x){
       for(auto i:edge[x]){
           DFS(i.first);        b[x]+=b[i.first];    }}signed main() {
       ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    cin>>n;    for(int i=1;i<=n;i++) cin>>a[i];    for(int i=2;i<=n;i++){
           int x,y;        cin>>x>>y;        edge[x].push_back({
   i,y});    }    dfs(1,0,0);    for(int i=2;i<=n;i++){
           sol(i);    }    DFS(1);    for(int i=1;i<=n;i++){
           cout<
      
       <<" ";    }}
      
     
    
   

转载地址：https://blog.csdn.net/xxxxxiao123/article/details/116452391 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！