题解：P14671 [ICPC 2025 Seoul R] Clean Arrangement

syk666 · 2026-03-24 11:04:31 · 题解

性质：子树具有最优子结构性。

证明：考虑子树放到当前根 rt 的左边，我们肯定会通过对称使得子树的根 x 靠近左边。代价由两部分组成：子树内部，rt-x。那么 x 往左移显然劣，往右移动 rt-x 减少 1，而由于 x 右边子树少，因此子树内答案至少 +1，因此绝对不优。

那么原问题转化为，当前 x 固定，子树分别放在左右两边，求最小的代价。

子树内部贡献不变，而其与 rt 中间每放一个子树，他的 len 就要累加。

因此考虑从两边往中间放即可，使得越大的子树加的次数越少即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int now[N],pre[N],to[N],tot=0;
int n;
int siz[N],rk[N],dp[N];
void add(int x,int y){
    tot++;
    to[tot]=y;
    pre[tot]=now[x];
    now[x]=tot;
}
struct Node{
    int siz,v;
}a[N];
int cnt=0;

bool cmp(Node A,Node B){
    return A.siz>B.siz;
}
void dfs(int x,int f){
    dp[x]=rk[x]=0;
    siz[x]=1;
    for(int i=now[x];i;i=pre[i]){
        int node=to[i];
        if(node==f) continue;
        dfs(node,x);
        siz[x]+=siz[node];
    }
    cnt=0;
    for(int i=now[x];i;i=pre[i]){
        int node=to[i];
        if(node==f) continue;
        a[++cnt]={siz[node],dp[node]+rk[node]};
    }   
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++){
        if(i%2==1) dp[x]+=a[i].siz*((i-1)/2)+a[i].v;
        else dp[x]+=a[i].siz*((i-1)/2)+a[i].v,rk[x]+=a[i].siz;
    }
    rk[x]++;
}
void solve(){
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    cout<<dp[1]<<endl;
}
int main(){
    int T=1;
//    scanf("%d",&T);
    while(T--) solve();
    return 0;
}