正题

题目链接:https://www.luogu.org/problem/CF613D

---

题目大意

一棵树，每次询问$k$个点，删除$m$个点要这些点两两不连通，求$m$的最小值。

---

解题思路

我们可以对于询问的点构造一颗虚树，然后进行贪心选取即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=110000; struct node{int to,next; }a[2*N]; int n,siz[N],dep[N],son[N],top[N],fa[N]; int tot,ls[N],p[N],ans,cnt,s[N],q,dfn[N],num; void adde(int x,int y) {if(x==y) return;a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dfs1(int x) {siz[x]=1;dfn[x]=++num; for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x]) continue;dep[y]=dep[x]+1;fa[y]=x;dfs1(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y; } } void dfs2(int x,int fa) {if(son[x]){top[son[x]]=top[x];dfs2(son[x],x);}for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||y==son[x]) continue;top[y]=y;dfs2(y,x);} } int LCA(int x,int y) {while(top[x]!=top[y])if(dep[top[x]]<dep[top[y]]) y=fa[top[y]];else x=fa[top[x]];if(dep[x]<dep[y]) return x;return y; } void ins(int x) {if(!cnt){s[++cnt]=x;return;}int lca=LCA(s[cnt],x);while(cnt>1&&dep[lca]<dep[s[cnt-1]]){adde(s[cnt-1],s[cnt]),cnt--;}if(dep[lca]<dep[s[cnt]]) adde(lca,s[cnt--]);if((!cnt)||(s[cnt]!=lca)) s[++cnt]=lca;s[++cnt]=x; } void dp(int x) {if(siz[x]){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dp(y);if(siz[y]){siz[y]=0;ans++;}}}else{for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dp(y);siz[x]+=siz[y];siz[y]=0;}if(siz[x]>1){ans++;siz[x]=0;}}ls[x]=0; } bool cmp(int x,int y) {return dfn[x]<dfn[y];} int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);adde(x,y);adde(y,x);}dfs1(1);top[1]=1;dfs2(1,1);tot=0;memset(siz,0,sizeof(siz));memset(ls,0,sizeof(ls));scanf("%d",&q);while(q--){int k;cnt=0;ans=0;scanf("%d",&k);p[0]=1;for(int i=1;i<=k;i++){scanf("%d",&p[i]);siz[p[i]]++;}for(int i=1;i<=k;i++)if(siz[fa[p[i]]]){puts("-1");p[0]=0;break;}if(!p[0]){for(int i=1;i<=k;i++)siz[p[i]]--;continue;}sort(p+1,p+1+k,cmp);if(p[1]!=1) s[++cnt]=1;for(int i=1;i<=k;i++) ins(p[i]);while(cnt>1) adde(s[cnt-1],s[cnt]),cnt--;dp(1);siz[1]=tot=0;printf("%d\n",ans);} }

总结

以上是生活随笔为你收集整理的CF613D-Kingdom and its Cities【虚树,LCA,树链剖分,贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。