【CF767C】Garland

传送门啦

分析：

这个题我是看着翻译做的，感觉不是很难，很普通的一个树形dp

题目大意：

在一棵树上分离出三个子树，使这三个子树的点权和相等。

明确题目意思这个题就简单多了吧。

我们会发现每一棵子树的点权是固定的，因为点权总和固定，设每一部分的大小为W，那么我们就从下往上更新（因为树形dp的基本做法就是从下向上更新，用儿子更新爸爸），遇到等于W的子树就切一刀，sz重置成0，这就可以一边遍历子树，一边算sz.

剪枝（额。。好像不能叫剪枝）也挺容易想，如果点权总和不是3的倍数，那么肯定不行（分不出三个相等）

这题细节挺多的，需要注意一条链的情况和和是三的倍数但不能分成几个相等的部分的情况。

最后的那个地方cnt >= 3就是想,如果分成了大于等于3个子树，就直接输出两个就行了，否则的话就输出-1，证明我们最多只能找到两个子树权值是整棵树的 1/3

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = ;

inline int read(){

    char ch = getchar();

    int f =  , x = ;

    while(ch > '' || ch < ''){if(ch == '-') f = -; ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int w[maxn],x,y;

int head[maxn],tot;

struct Edge{

    int from,to,val,next;

}edge[maxn<<];

int n,root,sum,sz[maxn],cnt,ans[];

void add(int u,int v){

    edge[++tot].from = u;

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot;

}

int dfs(int x,int fa){

    sz[x] = w[x];

    for(int i=head[x];i;i=edge[i].next){

        int v = edge[i].to;

        if(v != fa){

            dfs(v , x);

            sz[x] += sz[v];

        }

    }

    if(sz[x] == sum){

       ans[++cnt] = x;

       sz[x] = ;

    }

}

int main(){

    n = read();

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

        x = read(); y = read();

        if(x != )  add(i , x), add(x , i);

        else root = i;

        w[i] = y;

        sum += y;

    }

    if(sum %  != )  printf("-1\n");

    else {

        sum /= ;

        dfs(root , );

        if(cnt >= )  printf("%d %d\n",ans[],ans[]);

        else printf("-1\n");

    }

    return ;

}

巴特西

【CF767C】Garland

最新文章

热门文章