CF 1119F Niyaz and Small Degrees

打VP的时候由于CXR和XRY切题太快了导致我只能去写后面的题了

然而VP的时候大概还有一小时时想出了\(O(n^2\log n)\)的暴力，然后过了二十分钟才想到删点的优化

结果细节很多当然是写不出来的了，写完加调花了一个多小时吧，真的比赛时还是没什么用的说

首先我们讲一下暴力做法，考虑直接枚举最大的点度数，我们考虑DP删边，设\(f_{x,0/1}\)表示\(x\)的子树内所有点度数小于限制并且\(0/1\)表示与父亲的边是否选择的最小答案

考虑对于\(f_{x,0}\)转移，我们可以把一个点\(x\)的所有儿\(y\)按照\(f_{y,1}+v_{x,y}-f_{y,0}\)排序，然后选择前\(deg_x-lim\)小的\(f_{y,1}+v_{x,y}\)，剩下的选\(\min(f_{y,1}+v_{x,y},f_{y,0})\)

同理，对于\(f_{x,1}\)就是留出一个，选前\(deg_x-lim-1\)小的

但是容易发现这样的复杂度是\(O(n^2\log n)\)的，我们细细一想容易发现不合法的点数变得越来越少

换句话说，就是我们需要DP处理的点越来越少了，容易想到如果我们此时把不必要的点都删掉了，那么整个DP要遍历的点就是\(\sum_{i=0}^{n-1} \sum_{j=1}^n [i\le deg_j]=2n-2\)级别的

所以总体复杂度\(O(n\log n)\)，实现上用了multiset来代替可删除堆（怕手开两个优先队列太慢了）

CODE

#include<cstdio>

#include<vector>

#include<utility>

#include<set>

#include<algorithm>

#define RI register int

#define CI const int&

#define pb push_back

#define mp make_pair

#define fi first

#define se second

using namespace std;

const int N=250005;

typedef long long LL;

typedef pair <int,int> pi;

vector <pi> V[N]; vector <int> D[N],Ext[N]; multiset <LL> s[N];

LL sum[N],f[N][2],t,ans; int n,x,y,z,deg[N],pos[N],size[N]; bool vis[N];

inline void addedge(CI x,CI y,CI z)

{

    V[x].pb(mp(y,z)); ++deg[x]; V[y].pb(mp(x,z)); ++deg[y];

}

inline bool cmp(const pi& x,const pi& y)

{

    return deg[x.fi]<deg[y.fi];

}

inline int max(CI a,CI b)

{

    return a>b?a:b;

}

inline void insert(CI x,LL y)

{

    s[x].insert(y); ++size[x]; sum[x]+=y;

}

inline void remove(CI x,LL y)

{

    s[x].erase(s[x].find(y)); --size[x]; sum[x]-=y;

}

inline void DFS(CI now,CI lim)

{

    int td=deg[now]-lim; vis[now]=1; while (size[now]>max(td,0)) remove(now,*s[now].rbegin());

    while (pos[now]<deg[now]&&deg[V[now][pos[now]].fi]<=lim) ++pos[now];

    LL ret=0; vector <LL> TA,TB; for (RI i=pos[now];i<deg[now];++i)

    {

        int to=V[now][i].fi,val=V[now][i].se; if (vis[to]) continue; DFS(to,lim);

        if ((t=f[to][1]+val-f[to][0])<=0) --td,ret+=f[to][1]+val;

        else ret+=f[to][0],TA.pb(t),insert(now,t);

    }

    while (size[now]>max(td,0)) TB.pb(t=*s[now].rbegin()),remove(now,t); f[now][0]=ret+sum[now];

    while (size[now]>max(td-1,0)) TB.pb(t=*s[now].rbegin()),remove(now,t); f[now][1]=ret+sum[now];

	while (!TB.empty()) insert(now,TB.back()),TB.pop_back();

	while (!TA.empty()) remove(now,TA.back()),TA.pop_back();

}

int main()

{

    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

    RI i,j; for (scanf("%d",&n),i=1;i<n;++i)

    scanf("%d%d%d",&x,&y,&z),addedge(x,y,z),ans+=z;

    for (i=1;i<=n;++i) sort(V[i].begin(),V[i].end(),cmp);

    for (i=1;i<=n;++i) D[deg[i]].pb(i);

    for (i=1;i<=n;++i) for (j=1;j<deg[i];++j) Ext[j].pb(i);

    for (printf("%I64d ",ans),i=1;i<n;++i)

    {

        for (int x:D[i]) { vis[x]=1; for (pi it:V[x]) if (!vis[it.fi]) insert(it.fi,it.se); } ans=0;

        for (int x:Ext[i]) if (!vis[x]) DFS(x,i),ans+=f[x][0]; printf("%I64d ",ans); for (int x:Ext[i]) vis[x]=0;

    }

    return 0;

}

巴特西

CF 1119F Niyaz and Small Degrees

最新文章

热门文章