各大搜索引擎网站提交入口大全,北京网站排名公司,国外经典手机网站设计,现在网站的外部链接怎么做正题
luogu 7600[APIO 2021 T3] luogu-CF1119F 题目大意
给你一棵树#xff0c;给出每条边割掉的代价#xff0c;问你对于0⩽kn0\leqslant kn0⩽kn#xff0c;使得每个点的度数小于k的最小代价 解题思路
首先考虑单询问的情况
可以设fx,1/0f_{x,1/0}fx,1/0…正题
luogu 7600[APIO 2021 T3] luogu-CF1119F 题目大意
给你一棵树给出每条边割掉的代价问你对于0⩽kn0\leqslant kn0⩽kn使得每个点的度数小于k的最小代价 解题思路
首先考虑单询问的情况
可以设fx,1/0f_{x,1/0}fx,1/0表示第x个点到父节点的边连/不连的最小代价
对于点x最多连k个点那么要割掉至少degx−kdeg_x-kdegx−k个点
假设所有子节点都连计算出割掉某个子节点的连边的代价从连到不连−fson,1fson,0len-f_{son,1}f_{son,0}len−fson,1fson,0len然后从中选择degx−kdeg_x-kdegx−k个最小代价的点如果割掉更优则尽量割该操作可以用堆实现
当k较大时不难发现很多点已经满足deg⩽kdeg\leqslant kdeg⩽k的条件没有计算的意义
所以对于点xdegx⩽kdeg_x\leqslant kdegx⩽kx已经满足条件所以不用管该点然后在连接的点中加上该点对于这些点还有意义
对于每个点可以用两个堆维护一个可删堆对于degkdegkdegk的点用完后要删掉下一轮中数值会改变而对于deg⩽kdeg\leqslant kdeg⩽k的点,为数值不会改变所以不删
综上每轮将无用的点删掉然后计算有用的点 代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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;
};
vectorreca[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_queueintd1, 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;
}
