CF767C Garland 【树形dp】By cellur925

一句话题意：给定一个树，树有点权，要求把树的某些边删去，使树变成三个部分，每部分点权值和相等。

我们很容易想到，再读入的时候记录所有点的点权之和，点权除以3是最后权值相等的值。如果不能整除3一定无解，可以结束程序。

那么之后？

我们很自然地想到，状态可以设计为：f[i]为以i为根的子树上的点权和。边界为它自身点权（初值）。

转移也就很自然，f[i]=sigma f[j],j枚举i的儿子。但是很有可能儿子上的权值就满足最后的权值，我们就可以干掉这颗子树，继续遍历当前主树。最后两个断点就先从小子树中找到，再从较大子树中找到。

值得我们注意的是，这的确是一棵有根树，提链的老哥手里攥着的灯泡就是根，根是不能作为断点的。这点需要特别注意。

code

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 using namespace std;

 int n,sum,root;

 int x=-,y=-;

 int f[];

 int val[];

 vector<int>son[];

 void TreeDp(int u,int fa)

 {

     f[u]=val[u];

     for(int i=;i<son[u].size();i++)

     {

         int v=son[u][i];

         if(v==fa) continue;

         TreeDp(v,u);

         if(f[v]==sum&&y==-) y=v;

         else f[u]+=f[v];

     }

     if(f[u]==sum&&x!=root&&y!=-) x=u;

 }

 int main()

 {

     scanf("%d",&n);

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

     {

         int u=,w=;

         scanf("%d%d",&u,&w);

         sum+=w;

         if(u==) root=i;

         val[i]=w;

         son[u].push_back(i);

     }

 //    printf("%d\n",sum);

     if(sum%!=)

     {

         printf("-1");

         return ;

     }

     sum/=;

     TreeDp(root,-);

     if(x!=-&&x!=root) printf("%d %d",x,y);

     else printf("-1");

     return ;

 }

巴特西

CF767C Garland 【树形dp】By cellur925

最新文章

热门文章