D. Sum in the tree（树形+贪心）

题目链接;http://codeforces.com/contest/1099/problem/D

题目大意：给出一棵树，每个节点到根节点的路径上经过的所有点的权值之和，其深度为偶数的节点的信息全部擦除了，也就是用-1表示，让你求最终所有点权之和（要求最小）

具体思路：对于每一个节点，这个点到根节点的权值最小的时候是他的所有的根节点的最小值，然后一路更新上去就可以了，最后求值得时候，我们求父亲节点和子节点之间的差就可以了，如果差值为负值就是非法情况。

AC代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 # define ll long long
  4 # define inf 0x3f3f3f3f
  5 const int maxn = 1e5+100;
  6 const int mod = 1e9+7;
  7 int head[maxn],num,dp[maxn][3],flag=1,vis[maxn];
  8 struct node
  9 {
 10     int nex;
 11     int to;
 12 } edge[maxn*2];
 13 ll sum;
 14 void addedge(int fr,int to)
 15 {
 16     edge[num].to=to;
 17     edge[num].nex=head[fr];
 18     head[fr]=num++;
 19 }
 20 void dfs1(int fr,int rt)
 21 {
 22     if(dp[fr][0]==-1)
 23     {
 24         int minn=inf;
 25         for(int i=head[fr]; i!=-1; i=edge[i].nex)
 26         {
 27             int to=edge[i].to;
 28             if(to==rt)
 29                 continue;
 30             minn=min(minn,dp[to][0]);
 31         }
 32         dp[fr][0]=minn;
 33         //cout<<fr<<" "<<dp[fr][0]<<endl;
 34     }
 35     for(int i=head[fr]; i!=-1; i=edge[i].nex)
 36     {
 37         int to=edge[i].to;
 38         if(to==rt)
 39             continue;
 40         dfs1(to,fr);
 41         if(dp[to][0]==inf)
 42             dp[to][0]=dp[fr][0];
 43     }
 44 }
 45 void dfs2(int fr,int rt)
 46 {
 47     if(flag==0)
 48         return ;
 49     for(int i=head[fr]; i!=-1; i=edge[i].nex)
 50     {
 51         int to=edge[i].to;
 52         if(to==rt)
 53             continue;
 54             dfs2(to,fr);
 55         sum+=(dp[to][0]-dp[fr][0]);
 56         if(dp[to][0]-dp[fr][0]<0)
 57         {
 58             flag=0;
 59         }
 60 
 61     }
 62 }
 63 
 64 int main()
 65 {
 66     int n;
 67     scanf("%d",&n);
 68     for(int i=1; i<=n; i++)
 69     {
 70         head[i]=-1;
 71     }
 72     int tmp;
 73     for(int i=2; i<=n; i++)
 74     {
 75         scanf("%d",&tmp);
 76         addedge(tmp,i);
 77         addedge(i,tmp);
 78     }
 79     for(int i=1; i<=n; i++)
 80     {
 81         scanf("%d",&dp[i][0]);
 82     }
 83     dfs1(1,-1);
 84     dfs2(1,-1);
 85     sum+=dp[1][0];
 86     for(int i=1; i<=n; i++)
 87     {
 88      //   cout<<dp[i][0]<<endl;
 89     }
 90 //        for(int i=n-1; i>=1; i--)
 91 //        {
 92 //            sum+=(dp[i+1][0]-dp[i][0]);
 93 //            if(dp[i+1][0]-dp[i][0]<0)flag=0;
 94 //        }
 95     if(flag==0)
 96         sum=-1;
 97     printf("%lld
",sum);
 98     return 0;
 99 }
100 /*
101 5
102 1 2 2 3
103 1 -1 2 3 -1
104 3
105 */
106