P14346 题解

· · 题解

设 ans_x 为指定 x 座城市为度假城市的最小费用。x=1 的情况是平凡的，不妨假设 x\ge 2。

此时，我们找出包含所有选择的节点的最小连通块，把它缩成一个点，那么从它出发的外向生成树上所有边权之和就是答案。

先将条件加强为“包含所有选择的节点和根节点的最小连通块”。这样我们可以进行树形 dp：令 f_{u,i} 表示 u 子树内选择 i 个节点的最小代价（只考虑 u 子树内的边）。

因为需要包含根节点，所以 i>0 时 u 节点一定在连通块内；否则，u 子树中所有节点都不在连通块内，此时从 fa_u 连向 u 的边就会在向上转移的时候产生代价。

可以证明 f_u 是下凸的。从 f_v 向 f_u(u=fa_v) 转移时，f_{v,0} 会产生额外代价，这不影响凸性；而进行 (\min,+) 卷积也不影响凸性。

现在复杂度瓶颈是 O(n^2) 的卷积，但在函数有凸性的情况下可以维护差分数组进行归并——这里由于只有对 f_{v,0} 的修改，用可并堆维护，时间复杂度 O(n\log n)。

当然唯一的问题是我们选择的连通块不一定包含根节点——这可以用点分治解决。同时处理根节点时需要特判：前面两步必须选择两个不同子树中的节点，贪心即可。如果无法选出，那么当前子树至多有两个节点，这是简单的。

时间复杂度 O(n\log^2 n+Q)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=200007;
ll n,m,ans[N],p[N],f[N],root[N],val[N],lson[N],rson[N],sz[N],mx[N],vis[N];
vector<pair<ll,ll> > to[N];
map<pair<ll,ll>,ll> mp;
int merge(int u,int v){
    if (!u||!v){
        return u|v;
    }
    if (val[u]<val[v]){
        swap(u,v);
    }
    rson[u]=merge(rson[u],v);
    swap(lson[u],rson[u]);
    return u;
}
void reset(int u){
    val[u]=lson[u]=rson[u]=0;
}
int pop(int u){
    return merge(lson[u],rson[u]);
}
void getroot(int u,int fa,int n,int& r){
    sz[u]=1;mx[u]=0;
    for (auto p:to[u]){
        if (vis[p.first]||p.first==fa){
            continue;
        }
        int v=p.first;
        getroot(v,u,n,r);
        mx[u]=max(mx[u],sz[v]);
        sz[u]+=sz[v];
    }
    if (max(mx[u],n-sz[u])*2<=n){
        r=u;
    }
}
void dfs(int u,int fa){
    f[u]=0;root[u]=0;sz[u]=1;
    for (auto p:to[u]){
        if (vis[p.first]||p.first==fa){
            continue;
        }
        int v=p.first;
        dfs(v,u);
        sz[u]+=sz[v];
        f[u]+=f[v]+p.second;
        val[root[v]]+=p.second;
        if (fa){
            root[u]=merge(root[u],root[v]);
        }
    }
    if (root[u]==0&&fa){
        reset(u);
        root[u]=u;
    }
}
void solve(int u,int n,ll dif){
    if (n==1){
        ans[1]=min(ans[1],dif);
        vis[u]=1;
        return;
    }
    if (n==2){
        ans[2]=min(ans[2],dif);
        int v=0;
        for (auto p:to[u]){
            if (!vis[p.first]){
                v=p.first;
                ans[1]=min(ans[1],dif+p.second);
                ans[1]=min(ans[1],dif+mp[make_pair(v,u)]);
                vis[u]=vis[v]=1;
                return;
            }
        }
        return;
    }
    getroot(u,0,n,u);
    dfs(u,0);
    ans[1]=min(ans[1],f[u]+dif);
    int p1=0,p2=0;
    for (auto p:to[u]){
        if (vis[p.first]){
            continue;
        }
        int v=p.first;
        if (val[root[v]]>val[root[p2]]){
            p2=v;
        }
        if (val[root[p2]]>val[root[p1]]){
            swap(p1,p2);
        }
    }
    assert(p1&&p2);
    ll s=f[u]+dif-val[root[p1]]-val[root[p2]];
    ans[2]=min(ans[2],s);
    root[p1]=pop(root[p1]);root[p2]=pop(root[p2]);
    for (auto p:to[u]){
        if (vis[p.first]){
            continue;
        }
        root[u]=merge(root[u],root[p.first]);
    }
    for (int i=3;root[u];++i){
        s-=val[root[u]];
        root[u]=pop(root[u]);
        ans[i]=min(ans[i],s);
    }
    vis[u]=1;
    for (auto p:to[u]){
        if (vis[p.first]){
            continue;
        }
        int v=p.first;
        solve(v,sz[v],dif+f[u]-f[v]-p.second+mp[make_pair(v,u)]);
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    memset(ans,0x3f,sizeof(ans));
    for (int u,v,x,y,i=1;i<n;++i){
        cin>>u>>v>>x>>y;
        to[u].emplace_back(v,x);to[v].emplace_back(u,y);
        mp[make_pair(u,v)]=x;
        mp[make_pair(v,u)]=y;
    }
    solve(1,n,0);
    for (int i=2;i<=n;++i){
        ans[i]=min(ans[i],ans[i-1]);
    }
    cin>>m;
    for (int x,i=1;i<=m;++i){
        cin>>x;
        cout<<ans[x]<<'\n';
    }
    return 0;
}