正題

luogu 7600[APIO 2021 T3]
luogu-CF1119F

---

題目大意

給你一棵樹，給出每條邊割掉的代價，問你對于$0?k<n$，使得每個點的度數小于k的最小代價

---

解題思路

首先考慮單詢問的情況

可以設$f_{x,1/0}$表示第x個點到父節點的邊連/不連的最小代價

對于點x，最多連k個點，那么要割掉至少$de{g}_x?k$個點

假設所有子節點都連，計算出割掉某個子節點的連邊的代價（從連到不連，$?f_{son,1}+f_{son,0}+len$），然后從中選擇$de{g}_x?k$個最小代價的點（如果割掉更優則盡量割），該操作可以用堆實現

當k較大時，不難發現，很多點已經滿足$deg?k$的條件，沒有計算的意義

所以對于點x（$de{g}_x?k$），x已經滿足條件，所以不用管該點，然后在連接的點中加上該點（對于這些點還有意義）

對于每個點，可以用兩個堆維護一個可刪堆，對于$deg>k$的點，用完后要刪掉（下一輪中數值會改變），而對于$deg?k$的點,，為數值不會改變，所以不刪

綜上，每輪將無用的點刪掉，然后計算有用的點

---

代碼

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 500010 using namespace std; ll n, w, h, ans, summ; ll p[N], s[N], f[N][2], gt[N], addl[N], dell[N], deg[N]; struct lne {ll x, y, z; }l[N]; struct rec {ll to, l; }; vector<rec>a[N]; bool cmp(lne x, lne y) {return deg[x.y] > deg[y.y]; } bool cmpp(ll x, ll y) {return deg[x] < deg[y]; } struct heap//可刪堆 {priority_queue<int>d1, d2;ll sum;ll sz(){return d1.size() - d2.size();}void clear(){while(d1.size() && d2.size() && d1.top() == d2.top())d1.pop(), d2.pop();return;}void add(ll x){d1.push(x);sum += x;return; }void del(ll x){d2.push(x);sum -= x;clear();return;}void pop(){sum -= d1.top();d1.pop();clear();return;}ll top(){ll g = d1.top();pop();return g;} }d[N]; void dfs(ll x, ll fa, ll k) {p[x] = k;f[x][0] = f[x][1] = 0;for (int i = 0; i < a[x].size(); ++i){ll y = a[x][i].to;if (deg[y] <= k) break;if (y != fa)dfs(y, x, k);}ll an = 0, dn = 0, num = deg[x] - k;while(d[x].sz() > num) d[x].pop();for (int i = 0; i < a[x].size(); ++i){ll y = a[x][i].to, z = a[x][i].l;if (deg[y] <= k) break;if (y != fa){if (f[y][1] < f[y][0] + z)//計算代價{f[x][1] += f[y][1];d[x].add(-f[y][1] + f[y][0] + z);dell[++dn] = -f[y][1] + f[y][0] + z;}else num--, f[x][1] += f[y][0] + z;//代價小于1的就直接刪，而且要刪的邊少一條}}f[x][0] = f[x][1];while(d[x].sz() > max(num, 0ll))//已經刪的邊可能大于要刪的邊，所以要取maxaddl[++an] = d[x].top();f[x][1] += d[x].sum;while(d[x].sz() > max(num - 1, 0ll))addl[++an] = d[x].top();f[x][0] += d[x].sum;for (int i = 1; i <= an; ++i)d[x].add(addl[i]);//補回去for (int i = 1; i <= dn; ++i)d[x].del(dell[i]);return; } int main() {scanf("%lld", &n);for (ll i = 1; i < n; ++i){w++;scanf("%lld%lld%lld", &l[w].x, &l[w].y, &l[w].z);w++;l[w] = l[w - 1];swap(l[w].x, l[w].y);deg[l[w].x]++;deg[l[w].y]++;summ += l[w].z;}for (ll i = 1; i <= n; ++i)s[i] = i;sort(l + 1, l + 1 + w, cmp);//邊從小到大排，當枚舉一個點的連邊時，如果度數小于等于k，那么接下來的點都沒有意義sort(s + 1, s + 1 + n, cmpp);for (ll i = 1; i <= w; ++i)a[l[i].x].push_back((rec){l[i].y, l[i].z});printf("%lld", summ);h = 1;for (ll k = 1; k < n; ++k){ans = 0;while(deg[s[h]] <= k && h <= n)//沒用的點刪掉{for (ll i = 0; i < a[s[h]].size(); ++i)if (deg[a[s[h]][i].to] > k)d[a[s[h]][i].to].add(a[s[h]][i].l);else break;h++;}for (ll i = h; i <= n; ++i)if (p[s[i]] < k){dfs(s[i], 0, k);ans += f[s[i]][1];}printf(" %lld", ans);}return 0; }

總結

以上是生活随笔為你收集整理的【堆】【DP】Niyaz and Small Degrees（luogu 7600[APIO 2021 T3]/luogu-CF1119F）的全部內容，希望文章能夠幫你解決所遇到的問題。

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