首页 > 代码库 > CodeForces 767C Garland

CodeForces 767C Garland

树形$dp$。

先看权值之和是否为$3$的倍数,如果不是则一定无解。

如果是$3$的倍数,可以分两次去切。每次一个节点,要求这个节点不是根,并且的子树权值和为$sum/3$,又要是深度最深的。

找不到两个依然是无解,否则就有解。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c = getchar();    x = 0;    while(!isdigit(c)) c = getchar();    while(isdigit(c))    {        x = x * 10 + c - 0;        c = getchar();    }}int n,root,c[1000010],p[1000010],sum,ans1,ans2;vector<int >v[1000010];int flag1,flag2;void dfs1(int x){    c[x]=p[x];    for(int i=0;i<v[x].size();i++)    {        dfs1(v[x][i]); if(flag1) return ;        c[x]+=c[v[x][i]];    }    if(x!=root&&c[x]==sum/3)    {        flag1=1;        ans1=x;    }}void dfs2(int x){    c[x]=p[x];    for(int i=0;i<v[x].size();i++)    {        if(v[x][i]==ans1) continue;        dfs2(v[x][i]); if(flag2) return ;        c[x]+=c[v[x][i]];    }    if(x!=root&&c[x]==sum/3)    {        flag2=1;        ans2=x;    }}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        int fa; scanf("%d%d",&fa,&p[i]);        sum=sum+p[i];        if(fa==0) root=i;        else v[fa].push_back(i);    }    if(sum%3!=0)    {        printf("-1\n");        return 0;    }    dfs1(root);    if(flag1==0)    {        printf("-1\n");        return 0;    }    memset(c,0,sizeof c);    dfs2(root);    if(flag2==0)    {        printf("-1\n");        return 0;    }    else    {        printf("%d %d\n",ans1,ans2);    }    return 0;}

 

CodeForces 767C Garland