Codeforces Round #398 (Div. 2) C. Garland —

题目链接：http://codeforces.com/contest/767/problem/C

题解：类似于提着一串葡萄，用剪刀剪两条藤，葡萄分成了三串。问怎样剪才能使三串葡萄的质量相等。

首先要做的就是统计葡萄的总质量tot。之后就是找到两子串质量为（tot/3）的葡萄（如果除不尽，则必定找不到），那么剩下的就是dfs搜索了。

我一开始的做法是先建一棵记录子树质量和的树，然后再从上往下dfs，如果找到了，就把它剪掉。后来发现被剪掉的那一串可能就含有两串质量为（tot/3）的葡萄（这里质量可为负数），所以这种方法行不通。

那么正确的做法是先深入到最底层（叶子结点），然后再从下往上搜索，这个过程与建树的过程是一致的。所以可以将两个过程合并在一起。

代码如下：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<map>

 #include<string>

 #include<set>

 #define LL long long

 #define MAX(a,b) (a>b?a:b)

 #define MIN(a,b) (a<b?a:b)

 #define INF 0x7fffffff

 #define LNF ((1LL<<62)-1)

 #define maxn 200010

 using namespace std;

 int n, tot = ,cnt = , sum[], vis[];

 vector<int>child[];

 int ans[];

 int build(int rt)

 {

     vis[rt] = ;

     int m = child[rt].size();

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

     {

         if(!vis[child[rt][i]])

         sum[rt] += build(child[rt][i]);

         if(cnt==)

             return ;

     }

     if(sum[rt]==tot)

     {

         ans[cnt++] = rt;

         return ;

     }

     else return sum[rt];

 }

 int main()

 {

     int rt,v;

     scanf("%d",&n);

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

     {

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

         if(v)

         child[i].push_back(v);

         child[v].push_back(i);

         tot += sum[i];

         if(!v) rt = i, vis[rt] = ;

     }

     if(tot%)

     {

         puts("-1");

         return ;

     }

     tot /= ;

     int m = child[rt].size();

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

     {

         build(child[rt][i]);

         if(cnt==) break;

     }

     if(cnt==)

         printf("%d %d\n",ans[],ans[]);

     else

         puts("-1");

 }

巴特西

Codeforces Round #398 (Div. 2) C. Garland —— DFS

最新文章

热门文章