Codeforces 709E. Centroids 树形DP

题目链接：http://codeforces.com/contest/709/problem/E

题意：

　　给你一棵树，你可以任删一条边和加一条边，只要使得其仍然是一棵树，输出每个点是否都能成为重心

题解：

　　做题多动手，画一画；

　　假设要求当前节点i是否能经过操作成为重心，将它提起来为根，那么可以知道，就是选其中一颗子树提到以根为父亲的情况使得删去根之后每个子树点数和最多不超过n/2

　　回来看，这颗子树要么来自自身子树下，要么来自父亲节点，这个时候我们dfs出需要的东西，也就是能够提出来的子树点数和最大的且不超过n/2的那颗是多少，再进行判断

　　我的做法：找到每个节点以下的节点数目和能提出来的最多的数目以及最多和次多转移来的节点

#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 5e5+, maxn = 1e3+, mod = 1e9+, inf = 2e9;

vector<int > G[N];

int ans[N],submax[N],max1[N],max2[N],sz[N],n;

void dfs(int u,int f) {

    sz[u] = ;

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

        int to = G[u][i];

        if(to == f) continue;

        dfs(to,u);

        sz[u] += sz[to];

        if(submax[to] > submax[u]) {

            submax[u] = submax[to];

            max2[u] = max1[u];

            max1[u] = to;

        }

        else if(submax[max2[u]] < submax[to]) max2[u] = to;

    }

    if(sz[u] <= n/) submax[u] = sz[u];

}

void dfs(int u,int f,int pre) {

    int flag = ;

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

        int to = G[u][i];

        if(to == f) {

            int temp = n - sz[u];

            if(temp>n/ && temp - pre > n/) flag = ;

        }

        else {

            if(sz[to] > n/ && sz[to] - submax[to] > n/) flag = ;

        }

    }

    ans[u] = flag;

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

        int to = G[u][i];

        if(to == f) continue;

        int temp;

        if(n - sz[to] <= n/) temp = n - sz[to];

        else {

            if(to == max1[u]) temp = max(pre,submax[max2[u]]);

            else temp = max(pre,submax[max1[u]]);

        }

        dfs(to,u,temp);

    }

}

int main() {

    int u,v;

    scanf("%d",&n);

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

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

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(,);

    dfs(,,);

    for(int i = ; i <= n; ++i) cout<<ans[i]<<" ";

    return ;

}

巴特西

Codeforces 709E. Centroids 树形DP

最新文章

热门文章