题解：P17743 [ICPC 2019 Xuzhou R] Kill the tree

· · 题解

题意

题目描述：给出一棵树，求以每个节点为根节点的子树的所有重心

由我们熟悉的题目 CF685B 可知这题要用换根做。

:::success[一个重要的结论]{open} 一棵有根树的重心一定在根结点所在的重链上，一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。 :::

因此我们每次换根时只需要找到该节点的重儿子并暴力转移即可，时间复杂度近似 O(n) 。

:::success[Code]

// I often find myself reminiscing about the past.
// Moments of life freeze in my mind.
// I cut, fold, and curl the time behind me, kneading it into the white clouds drifting across the sky.
// Even clouds have their distinctions: cumulus clouds are heavy, while cirrus clouds are ethereal.
// The moments in life that strike me with awe pass through my thoughts and remain unforgettable forever, while the more ordinary, everyday memories leave behind only fragments under the erosion of time.
// Reminiscence is like entering a dream—too clear, and it cannot delight my imagination; too vague, and it sinks into nothingness.
// Only the mist-shrouded mountains and rivers, the veiled woman—that perfect haziness—can satisfy my longing for beauty.
// Reminiscence always wraps me, unbidden, in the yellowed pages of the past.
// Friends parted and reunited, streets demolished and rebuilt—each clue helps me set out from a specific moment and sail upstream against the river of time.
// The days gone by cannot be relived; I am merely a passerby.
// Yet I still long to leave myself moments of leisure on every journey into memory—to pause before a scene, to gaze across the haze of years at my former self, and to savor as much sweetness as I can.
// If beautiful times once flowed through my body, I am already content.
// The past has solidified.
// I carry my memories forward, but I often neglect to tend to them, and so the memories themselves keep changing their forms.
// This brings a certain challenge to my journeys of recollection.
// Where should I linger? I ask myself.

#include <bits/stdc++.h>
#define LOCAL

namespace ly {
    // 苦情巨树啊
    // 你听见了吗
    // 如果我也已经爱上了他
    // 我愿意用我们相识的一点一滴以及我的全部妖力来起誓
    // 让我们来生相见吧
    namespace IO {
        #ifndef LOCAL
            constexpr auto maxn = 1 << 21;
            char in[maxn], out[maxn], *p1 = in, *p2 = in, *p3 = out;
            #define getchar() (p1 == p2 && (p2 = (p1 = in) + fread(in, 1, maxn, stdin), p1 == p2) ? EOF : *p1++)
            #define flush() (fwrite(out, 1, p3 - out, stdout))
            #define putchar(x) (p3 == out + maxn && (flush(), p3 = out), *p3++ = (x))
            class Flush{ public: ~Flush(){ flush(); } } _;
        #endif
        namespace usr {
            template <typename type>
            inline type read(type &x){
                x = 0; bool flag(0); char ch = getchar();
                while(!isdigit(ch)) flag ^= ch == '-', ch = getchar();
                while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
                return flag ? x = -x : x;
            }
            template <typename type>
            inline void write(type x){
                x < 0 ? x = -x, putchar('-') : 0;
                static short Stack[50], top(0);
                do Stack[++top] = x % 10, x /= 10; while(x);
                while(top) putchar(Stack[top--] | 48);
            }
            inline char read(char &x){
                do x = getchar(); while(isspace(x));
                return x;
            }
            inline char write(const char &x){
                return putchar(x);
            }
            inline void read(char *x){
                static char ch;
                read(ch);
                do *(x++) = ch; while(!isspace(ch = getchar()) && ~ch);
            }
            template <typename type> inline void write(type *x){
                while(*x) putchar(*(x++));
            }
            inline void read(std::string &x){
                static char ch; read(ch), x.clear();
                do x += ch; while(!isspace(ch = getchar()) && ~ch);
            }
            inline void write(const std::string &x){
                for(int i = 0, len = x.length(); i < len; ++i) putchar(x[i]);
            }
            template <typename type, typename...T> inline void read(type &x, T&...y){
                read(x), read(y...);
            }
            template <typename type, typename...T>
            inline void write(const type &x, const T&...y){
                write(x), putchar(' '), write(y...), sizeof...(y) ^ 1 ? 0 : putchar('\n');
            }
            template <typename type>
            inline void put(const type &x, bool flag = 0){
                write(x), flag ? putchar('\n') : putchar(' ');
            }
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    } using namespace IO::usr;
} using namespace ly::IO::usr;

#define FILE
#define IOS() std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0)
#define mp std::make_pair
#define re register
using ll = long long;
using ull = unsigned long long;
using ld = double;
#define int long long
using pii = std::pair <int, int>;

constexpr int N = 1e6 + 5;
std::basic_string <int> G[N], hv[N];
int sz[N], fa[N], son[N], ans[N];
void dfs1(int u){
    sz[u] = 1, son[u] = -1;
    for(auto v : G[u]){
        if(v ^ fa[u]){
            fa[v] = u, dfs1(v), sz[u] += sz[v];
            if(son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
        }
    }
}
void dfs2(int u){
    ans[u] = u;
    for(auto v : G[u]) if(v ^ fa[u]) dfs2(v);
    if(~son[u]) ans[u] = ans[son[u]];
    while(sz[ans[u]] * 2 <= sz[u]){
        if(sz[ans[u]] * 2 == sz[u]) hv[u] += ans[u];
        ans[u] = fa[ans[u]];
    }
    hv[u] += ans[u];
}

signed main(){
    #ifndef FILE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    int n;
    read(n);
    for(int i = 1, u, v; i < n; ++i) read(u, v), G[u] += v, G[v] += u;
    dfs1(1), dfs2(1);
    for(int i = 1; i <= n; ++i){
        std::sort(hv[i].begin(), hv[i].end());
        for(auto v : hv[i]) put(v);
        putchar('\n');
    }
    return 0;
}

// 阿乌拉,投降吧
// ......
// 阿乌拉,站在你面前的是活了上千年的魔法使

:::