Codeforces Global Round 2 1119 F. Niyaz and Small Degrees

题意

现在给你一颗树，边有边权
回答$n$个询问，分别是对于$x=0,1,2..(n?1)$
使得每个点的度数都不超过$x$，最小化删掉的权值

题解

终于补完这题了，来写一下题解

我们先来考虑，对于单个$x$怎么做
显然可以DP
$f_{i,0/1}$表示以$i$这个节点为根的子树里面，$i$和他父亲的边不断/断的最优代价
至于转移的话，显然可以讨论转移，但是这里考虑一个看起来更可以维护的东西
假设，我们有$f_{j,1}+w\le f_{j,0}$
也就是断了这个肯定更优，那么对于$i$这个节点一定也是断掉这条边的
那么就先加上这个的贡献，然后$i$的度数–
否则的话，我们先假设这条边没有断，也就是加上$f_{j,0}$的代价
最后，$i$的度数可能不符合条件，设还需要断掉$num$条边
那么显然是将若干个$f_{j,0}$变为$f_{j,1}$
于是对于每一个节点维护一个$f_{j,1}+c?f_{j,0}$的堆，取$num$个小的就可以了
这里的堆，就是维护一下可以通过增加什么代价使得度数减$1$

考虑多个询问怎么做
按$x$从小到大做
可以发现，如果一个点的度数如果不比$x$大，那么他其实没什么决策的价值
因为选和不选不取决于他了，于是把他删掉，并把以他为端点的边直接丢到另外一个端点的堆里面
表示可以通过断这条边，来使得度数减1
然后剩下的，就只对需要决策的点做上面的DP
一个一个连通块做，然后就没什么了

堆的实现有点技巧，具体来说，就是维护一个sum，表示堆里面的和
然后我们强行让堆里面只有num个元素即可
当然，对于DP时候对堆的修改，要还原
但是无用点加入的边，不需要还原
这里可能有点歧义，具体看代码把

当然，可以使用splay或treap来维护，那么就只需要一个前$k$大的和，在平衡树上二分即可

至于复杂度，显然就是$$\sum _{i=0}^{n?1}\sum _{j=1}^n[i\le d_j]$$
其中$d$是度数
显然，这个式子就是所有节点的度数和，也就是$2n$级别
那么总的复杂度就是$nlogn$的了

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue> 
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PI;
const LL N=250005;
LL n;
vector<PI> e[N];
vector<LL> vec[N];
LL du[N];
bool cmp (PI x,PI y)	{
    return du[x.first]<du[y.first];}
LL nxt[N];
struct qq
{
    priority_queue<LL> A,B;void push (LL x)	{
    A.push(x);}void del (LL x)	{
    B.push(x);}LL top ()	{
    while (!B.empty()&&A.top()==B.top()) A.pop(),B.pop();return A.top();}void pop ()	{
    top();A.pop();}LL size() {
    return A.size()-B.size();}
}h[N];
bool vis[N];
LL sum[N]; 
void upd (LL x,LL num)	
{
    while (h[x].size()>num)	{
    sum[x]=sum[x]-h[x].top();h[x].pop();}
}
void upd1 (LL x,LL num,vector<LL> & add)
{
    while (h[x].size()>num)	{
    sum[x]=sum[x]-h[x].top();add.push_back(h[x].top());h[x].pop();}
}
void dele (LL x)
{
    vis[x]=true;for (LL u=0;u<e[x].size();u++){
    LL y=e[x][u].first,c=e[x][u].second;	if (vis[y]) continue;h[y].push(c);	sum[y]=sum[y]+c;}
}
LL f[N][2],D;
LL st[N];
void dfs (LL x)
{
    vis[x]=true;LL num=du[x]-D;	upd(x,num);vector<LL> add,del;add.clear();del.clear();LL siz=e[x].size(),tot=0;while (st[x]<siz&&du[e[x][st[x]].first]<=D) st[x]++;for (LL u=st[x];u<siz;u++){
    LL y=e[x][u].first,c=e[x][u].second;if (vis[y]) continue;dfs(y);if (f[y][1]+c<=f[y][0])	{
    num--;tot=tot+f[y][1]+c;}else{
    tot=tot+f[y][0];LL o=f[y][1]+c-f[y][0];del.push_back(o);	h[x].push(o);sum[x]=sum[x]+o;}}upd1(x,max(0LL,num),add);f[x][0]=tot+sum[x];upd1(x,max(0LL,num-1),add);f[x][1]=tot+sum[x];for (LL u=0;u<add.size();u++) h[x].push(add[u]),sum[x]+=add[u];for (LL u=0;u<del.size();u++) h[x].del(del[u]),sum[x]-=del[u];
}
int main()
{
    scanf("%lld",&n);LL ans=0;for (LL u=1;u<n;u++){
    LL x,y,c;scanf("%lld%lld%lld",&x,&y,&c);e[x].push_back({
    y,c});e[y].push_back({
    x,c});du[x]++;du[y]++;ans=ans+c;}printf("%lld ",ans);for (LL u=1;u<=n;u++){
    vec[du[u]].push_back(u);sort(e[u].begin(),e[u].end(),cmp);}nxt[n]=n+1;for (LL u=n-1;u>=1;u--){
    if (vec[u+1].size()) nxt[u]=u+1;else nxt[u]=nxt[u+1];}memset(vis,false,sizeof(vis));for (LL u=1;u<n;u++){
    for (LL i=0;i<vec[u].size();i++) dele(vec[u][i]);ans=0;D=u;for (LL i=u+1;i<=n;i=nxt[i])	for (LL j=0;j<vec[i].size();j++){
    if (vis[vec[i][j]]==true) continue;dfs(vec[i][j]);ans=ans+f[vec[i][j]][0];}for (LL i=u+1;i<=n;i=nxt[i])	for (LL j=0;j<vec[i].size();j++)	vis[vec[i][j]]=false;printf("%lld ",ans);}return 0;
}