正題

題目鏈接:https://www.luogu.com.cn/problem/P7600

---

題目大意

給出$n$個點的一棵樹，邊有邊權，對于每個$k$求去掉最小邊權和的點使得每個點的度數都不超過$k$。

$1\le n\le 10^5$

---

題目大意

APIO遇到的原題，和CF1119F一樣，感覺要被沖爛。

先考慮暴力的做法，設$f_{i,0/1}$表示點$i$割不割連接父節點的邊時滿足子樹條件的最小代價，然后對于每個點把每個兒子割掉的代價排個序取最小的一部分就好了，這樣時間復雜度$O(n^2)$的。

然后優化的話，發現當$k$比較大時有很大一部分的點是沒有作用的，所以可以考慮刪除一些沒有用的點。度數小于等于$k$的點直接刪去，這樣的話如果我們就能做到枚舉每個沒有被刪去的點，因為所有點的度數和為$2n$，這樣的復雜度是$O(n)$的。

刪除的點我們把代價加入父節點處維護的一個堆中，然后每次取出前一部分的點就好了，時間復雜度$O(n\log n)$。

---

還是貼CF那題的代碼吧，APIO的那個東西好丑（

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<set> #define ll long long #define mp(x,y) make_pair(x,y) using namespace std;const ll N=3e5+10;struct Heap{priority_queue<ll> q1,q2;ll sum;void Push(ll x){q1.push(x);sum+=x;return;}void Pop(ll x){q2.push(x);sum-=x;return;}ll Top(){while(!q2.empty()&&q1.top()==q2.top())q1.pop(),q2.pop();ll w=q1.top();q1.pop();sum-=w;return w;}ll Size(){return q1.size()-q2.size();} }q[N]; struct node{ll to,next,w; }a[N<<1]; ll n,tot,deg[N],f[N][2],ls[N],p[N],v[N]; set<pair<ll,ll> > s[N];queue<ll> cl,del;vector<ll> ans;void addl(ll x,ll y,ll w){a[++tot].to=y;deg[y]++;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot;return; } void dfs(ll x,ll fa,ll k){f[x][0]=f[x][1]=0;v[x]=k;ll siz=deg[x],S=0;while(q[x].Size()>siz-k)q[x].Top();set<pair<ll,ll> >::iterator it;for(it=s[x].begin();it!=s[x].end();it++){ll y=(*it).first;if(y==fa)continue;dfs(y,x,k);}for(it=s[x].begin();it!=s[x].end();it++){ll y=(*it).first;if(y==fa)continue;ll w=f[y][1]-f[y][0]+(*it).second;if(w<=0){S+=f[y][1]+(*it).second;siz--;continue;}S+=f[y][0];q[x].Push(w);del.push(w);}while(q[x].Size()>max(siz-k,0ll)){ll w=q[x].Top();cl.push(w);}f[x][0]=S+q[x].sum;while(q[x].Size()>max(siz-k-1,0ll)){ll w=q[x].Top();cl.push(w);}f[x][1]=S+q[x].sum;while(!cl.empty())q[x].Push(cl.front()),cl.pop();while(!del.empty())q[x].Pop(del.front()),del.pop();return; } bool cmp(ll x,ll y) {return deg[x]<deg[y];} signed main(){scanf("%lld",&n);for(ll i=1;i<n;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);addl(x,y,w);addl(y,x,w);s[x].insert(mp(y,w));s[y].insert(mp(x,w));}for(ll i=1;i<=n;i++)p[i]=i;sort(p+1,p+n+1,cmp);ll z=1;memset(v,-1,sizeof(v));for(ll k=0;k<n;k++){if(k>=deg[p[n]]){ans.push_back(0);continue;}while(z<=n&&deg[p[z]]<=k){ll x=p[z];for(ll i=ls[x];i;i=a[i].next)if(deg[a[i].to]>k){q[a[i].to].Push(a[i].w);s[a[i].to].erase(mp(x,a[i].w));}z++;}ll sum=0;for(ll i=z;i<=n;i++)if(v[p[i]]!=k)dfs(p[i],-1,k),sum+=f[p[i]][0];ans.push_back(sum);}for(ll i=0;i<ans.size();i++)printf("%lld ",ans[i]); }

總結

以上是生活随笔為你收集整理的P7600-[APIO2021]封闭道路【堆,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。