CF708C Centroids(树形DP)

发现变重心就是往重心上割，所以\(\text{up and down}\)，一遍统计子树最大\(size\)，一遍最优割子树，\(down\)，\(up\)出信息，最后\(DFS\)出可行解

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#define R(a,b,c) for(register int a = (b); a <= (c); ++a)
#define nR(a,b,c) for(register int a = (b); a >= (c); --a)
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define MP make_pair
#ifdef QWQ
#define D_e_Line printf("\n------\n")
#define D_e(x) cerr << (#x) << " " << x << endl
#define C_e(x) cout << (#x) << " " << x << endl
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#define Pause() system("pause")
#include <cassert>
#define PASS fprintf(stderr, "Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#else
#define D_e_Line
#define D_e(x)
#define C_e(x)
#define FileOpen()
#define FileSave()
#define Pause()
#define PASS
#endif
using namespace std;
struct FastIO {
    template<typename ATP> inline FastIO& operator >> (ATP &x) {
        x = 0; int sign = 1; char c;
        for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') sign = -1;
        while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
        if(sign == -1) x = -x;
        return *this;
    }
} io;
template<typename ATP> inline ATP Max(ATP x, ATP y) {
    return x > y ? x : y;
}
template<typename ATP> inline ATP Min(ATP x, ATP y) {
    return x < y ? x : y;
}
template<typename ATP> inline ATP Abs(ATP x) {
    return x < 0 ? -x : x;
}
#include <vector>
const int N = 4e5 + 7;
vector<int> G[N];
int siz[N], maxSize[N], pos[N], down[N], up[N], n, halfSize;
inline void DFS_First(int u, int father) {
    siz[u] = 1, maxSize[u] = 0;
    for(auto v : G[u]){
        if(v == father) continue;
        DFS_First(v, u);
        siz[u] += siz[v];
        maxSize[u] = Max(maxSize[u], siz[v]);
    }
    maxSize[u] = Max(maxSize[u], n - siz[u]);
}
inline void DFS_WhichBigger(int u, int father) {
    for(auto v : G[u]){
        if(v == father || siz[v] < halfSize) continue;
        pos[u] = v;
        DFS_WhichBigger(v, u);
    }
}
inline void Down(int u, int father) {
    for(auto v : G[u]){
        if(v == father) continue;
        Down(v, u);
        down[u] = Max(down[u], down[v]);
    }
    if(siz[u] <= halfSize)
        down[u] = siz[u];
}
inline void Up(int u, int father) {
    pair<int,int> fir(0, 0), sec(0, 0);
    for(auto v : G[u]){
        if(v == father) continue;
        if(down[v] > fir.first){
            sec = fir, fir = MP(down[v], v);
        }
        else if(down[v] > sec.first){
            sec = MP(down[v], v);
        }
    }
    for(auto v : G[u]){
        if(v == father) continue;
        up[v] = Max(up[u], v == fir.second ? sec.first : fir.first);
        if(n - siz[v] <= halfSize){
            up[v] = Max(up[v], n - siz[v]);
        }
        Up(v, u);
    }
}
bool ans[N];
inline void DFS_Second(int u, int father) {
    if(maxSize[u] <= halfSize) ans[u] = true;
    else{
        if(pos[u]){
            ans[u] = (siz[pos[u]] - down[pos[u]] <= halfSize);
        }
        else{
            ans[u] = (n - siz[u] - up[u] <= halfSize);
        }
    }
    for(auto v : G[u]){
        if(v == father) continue;
        DFS_Second(v, u);
    }
}
int main() {
FileOpen();
    io >> n;
    halfSize = n >> 1;
    R(i,2,n){
        int u, v;
        io >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    DFS_First(1, 1);
    DFS_WhichBigger(1, 1);
    Down(1, 1);
    Up(1, 1);
    DFS_Second(1, 0);
    R(i,1,n) printf("%d ", ans[i]);
    return 0;
}

CF708C Centroids(树形DP)

原文：https://www.cnblogs.com/bingoyes/p/11851358.html