好后悔考场没思考这道最良心的水题...t1花了我两个半点结果连20都拿不到

哭了

题目描述：略

思路：将一个点下面的几条链合并成一条

 

用长链剖分的话似乎可以简化操作

实在太水了所以没啥好说的...

1 #include
     
       2 #include
      
        3 using std::priority_queue; 4 typedef long long lint; 5 const int N=200011; 6 template
       
         st max(st a,st b){
   return a>b?a:b;} 7 int n; 8 lint v[N]; 9 struct sumireko10 {11     int to,ne;12 }e[N];13 int he[N],ecnt;14 void addline(int f,int t)15 {16     e[++ecnt].to=t;17     e[ecnt].ne=he[f];18     he[f]=ecnt;19 }20 int fa[N],len[N],top[N],dson[N];21 void dfs1(int x)22 {23     len[x]=1;24     for(int i=he[x],t;i;i=e[i].ne)25     {26         t=e[i].to;27         if(t==fa[x]) continue;28         dfs1(t);29         if(len[t]>=len[x])30         {31             dson[x]=t;32             len[x]=len[t]+1;33         }34     }35 }36 priority_queue
        
          q[N];37 lint sta[N],hop;38 void dfs2(int x,int tt)39 {40     top[x]=tt;41     if(dson[x])42     {43         dfs2(dson[x],tt);44         for(int i=he[x],t;i;i=e[i].ne)45         {46             t=e[i].to;47             if(t==fa[x]||t==dson[x]) continue;48             dfs2(t,t);49             for(int j=1;j<=len[t];j++)50             {51                 lint a=q[tt].top(),b=q[t].top();52                 q[tt].pop(),q[t].pop();53                 sta[++hop]=max(a,b);54             }55             while(hop)56             {57                 q[tt].push(sta[hop--]);58             }59         }60     }61     q[tt].push(v[x]);62 }63 64 int main()65 {66     scanf("%d",&n);67     for(int i=1;i<=n;i++) scanf("%lld",&v[i]);68     for(int i=2;i<=n;i++)69     {70         scanf("%d",&fa[i]);71         addline(fa[i],i);72     }73     dfs1(1);74     dfs2(1,1);75     lint ans=0;76     while(!q[1].empty())77     {78         ans+=q[1].top();79         q[1].pop();80     }81     printf("%lld\n",ans);82     return 0;83 }