G6026 [GESP202609 六级] 分树规划 题解

知识点：树遍历、子树大小、最值。

解题思路

从根遍历建立父节点与顺序，再逆序累计子树大小。对每条父子边，删除后两部分大小为sz[u]和n-sz[u]，取差值绝对值最小。

为什么正确

树删一条边恰分成子树与其补集，所有非根节点一一对应全部可删边，因此枚举完备。

易错点

根没有父边，不应作为切边候选；先得到孩子的最终大小再合并到父亲。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>g(n+1);
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>p(n+1),q= {
        1
    }
    ,sz(n+1,1);
    for(int i=0;i<(int)q.size();i++) {
        int u=q[i];
        for(int v:g[u])if(v!=p[u]) {
            p[v]=u;
            q.push_back(v);
        }
    }
    int ans=n;
    for(int i=n-1;i>0;i--) {
        int u=q[i];
        ans=min(ans,abs(n-2*sz[u]));
        sz[p[u]]+=sz[u];
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。