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

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

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

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

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define ll long long

 # define inf 0x3f3f3f3f

 const int maxn = 1e5+;

 const int mod = 1e9+;

 int head[maxn],num,dp[maxn][],flag=,vis[maxn];

 struct node

 {

     int nex;

     int to;

 } edge[maxn*];

 ll sum;

 void addedge(int fr,int to)

 {

     edge[num].to=to;

     edge[num].nex=head[fr];

     head[fr]=num++;

 }

 void dfs1(int fr,int rt)

 {

     if(dp[fr][]==-)

     {

         int minn=inf;

         for(int i=head[fr]; i!=-; i=edge[i].nex)

         {

             int to=edge[i].to;

             if(to==rt)

                 continue;

             minn=min(minn,dp[to][]);

         }

         dp[fr][]=minn;

         //cout<<fr<<" "<<dp[fr][0]<<endl;

     }

     for(int i=head[fr]; i!=-; i=edge[i].nex)

     {

         int to=edge[i].to;

         if(to==rt)

             continue;

         dfs1(to,fr);

         if(dp[to][]==inf)

             dp[to][]=dp[fr][];

     }

 }

 void dfs2(int fr,int rt)

 {

     if(flag==)

         return ;

     for(int i=head[fr]; i!=-; i=edge[i].nex)

     {

         int to=edge[i].to;

         if(to==rt)

             continue;

             dfs2(to,fr);

         sum+=(dp[to][]-dp[fr][]);

         if(dp[to][]-dp[fr][]<)

         {

             flag=;

         }

     }

 }

 int main()

 {

     int n;

     scanf("%d",&n);

     for(int i=; i<=n; i++)

     {

         head[i]=-;

     }

     int tmp;

     for(int i=; i<=n; i++)

     {

         scanf("%d",&tmp);

         addedge(tmp,i);

         addedge(i,tmp);

     }

     for(int i=; i<=n; i++)

     {

         scanf("%d",&dp[i][]);

     }

     dfs1(,-);

     dfs2(,-);

     sum+=dp[][];

     for(int i=; i<=n; i++)

     {

      //   cout<<dp[i][0]<<endl;

     }

 //        for(int i=n-1; i>=1; i--)

 //        {

 //            sum+=(dp[i+1][0]-dp[i][0]);

 //            if(dp[i+1][0]-dp[i][0]<0)flag=0;

 //        }

     if(flag==)

         sum=-;

     printf("%lld\n",sum);

     return ;

 }

 /*

 5

 1 2 2 3

 1 -1 2 3 -1

 3

 */

巴特西

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

最新文章

热门文章