ABC291Ex 题解

sunkuangzheng · 2024-02-16 13:19:31 · 题解

我们先忽略第一条限制，只考虑第二条限制。

很自然想到树的重心，我们知道一棵树重心为根时，最大的子树的 siz_v \le \dfrac{1}{2}siz_u。类似点分治的，找到重心后断开，会分出若干子树，找子树重心是子问题，可以递归处理。

我们可以通过上面的方式，把重心之间连边，得到一棵新树。如果你这么写并直接提交，会发现已经 AC 了。现在我们来证明它满足第一条限制。

证明其实比较简单：x,y 在新树上的 LCA 一定是它们第一次被分开的那个重心，那么 x,y 在原树上的路径就一定经过这个重心，否则就不会被分开了。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,vis[N],u,v,siz[N],mx[N],rt,fa[N]; vector<int> g[N];
void dfs1(int u,int f){
    siz[u] = 1,mx[u] = 0;
    for(int v : g[u]) if(!vis[v] && v != f) dfs1(v,u),siz[u] += siz[v],mx[u] = max(mx[u],siz[v]);
}void getrt(int u,int f,int tot){
    mx[u] = max(mx[u],tot - siz[u]);
    if(mx[u] < mx[rt]) rt = u;
    for(int v : g[u]) if(!vis[v] && v != f) getrt(v,u,tot);
}void dfs2(int u){
    vis[u] = 1;
    for(int v : g[u]) if(!vis[v]) rt = 0,dfs1(v,0),getrt(v,0,siz[v]),fa[rt] = u,dfs2(rt);
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n; mx[0] = 1e9;
    for(int i = 1;i < n;i ++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
    dfs1(1,0),getrt(1,0,n),fa[rt] = -1,dfs2(rt);
    for(int i = 1;i <= n;i ++) cout << fa[i] << " ";
}

PS：我 AC 以后看别的题解，才知道我口胡的这东西就是点分树（