上海网站改版方案,如何在网站做广告,常宁网站制作,中国最有名的网站建设公司正题
jzoj题目链接:https://jzoj.net/senior/#main/show/5455 题目大意
一棵树中选k个点要求留下最小边使每个点都至少有一个点连接。 解题思路
我们先不考虑树的限制#xff0c;那么k个点满足要求的话最小边数为(k1)/2(k1)/2(k1)/2#xff0c;然后我们考虑一颗树上有多少…正题
jzoj题目链接:https://jzoj.net/senior/#main/show/5455 题目大意
一棵树中选k个点要求留下最小边使每个点都至少有一个点连接。 解题思路
我们先不考虑树的限制那么k个点满足要求的话最小边数为(k1)/2(k1)/2(k1)/2然后我们考虑一颗树上有多少个这样的点对满足。也就是选择最多的边数使得每条边两边的点都不重复。
当然这样的话每条边选最下面的边是最优的这时候我们就要知道输入保证了一个点的父亲的编号小与他所以我们按照这个加边顺序倒着枚举点就保证了每次加他和他父亲是最优的了。
然后如果有还不足的就一点对一边就好了。 code
#includecstdio
#includecstring
#includealgorithm
#define N 110000
using namespace std;
int fa[N],t,n,k,x,v[N],ans;
int read(){char cgetchar();int x0;for(;0c||c9;cgetchar());for(;0cc9;cgetchar()) xx*10(c-0);return x;
}
int main()
{freopen(init.txt,r,stdin);//freopen(tree.out,w,stdout);scanf(%d,t);for(int ti1;tit;ti){memset(v,0,sizeof(v));scanf(%d%d,n,k);ans0;for(int i2;in;i)fa[i]read();for(int in;i1;i--)if(!v[i]!v[fa[i]]) ans,v[fa[i]]true;//允许加边if(ans*2k) ansk-ans*2;//点对不足else if(ans*2k) ans-(ans*2-k)/2;//点对超过printf(%d\n,ans);}
}
