codeforces 682C Alyona and the Tree DFS-白红宇

codeforces 682C Alyona and the Tree DFS

阅读量：5130 次

发布时间：2019-06-13

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

这个题就是在dfs的过程中记录到根的前缀和，以及前缀和的最小值

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;typedef long long LL;const int N=1e5+5;const int INF=0x3f3f3f3f;const int mod=1e9+7;struct Edge{ int v,w,next;}edge[N<<1];int head[N],tot,a[N],n;bool del[N];void add(int u,int v,int w){ edge[tot].v=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++;}int ret;void dfs(int u,int f,LL cur,LL mn){ if(del[f])del[u]=true,++ret; else if(cur-mn>a[u])del[u]=true,++ret; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(v==f)continue; dfs(v,u,cur+1ll*edge[i].w,min(cur+1ll*edge[i].w,mn)); }}int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&a[i]); memset(head,-1,sizeof(head)); for(int i=2;i<=n;++i){ int u=i,v,w; scanf("%d%d",&v,&w); add(u,v,w);add(v,u,w); } dfs(1,0,0,0); printf("%d\n",ret); return 0;}