tk网站域名注册,网络工程是什么,网站建设管理措施,网页建站要多久正题
题目链接:https://www.luogu.org/problem/CF613D 题目大意
一棵树#xff0c;每次询问kkk个点#xff0c;删除mmm个点要这些点两两不连通#xff0c;求mmm的最小值。 解题思路
我们可以对于询问的点构造一颗虚树#xff0c;然后进行贪心选取即可。 codecodecode
#…正题
题目链接:https://www.luogu.org/problem/CF613D 题目大意
一棵树每次询问kkk个点删除mmm个点要这些点两两不连通求mmm的最小值。 解题思路
我们可以对于询问的点构造一颗虚树然后进行贪心选取即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N110000;
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(xy) return;a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs1(int x)
{siz[x]1;dfn[x]num; for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[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 ils[x];i;ia[i].next){int ya[i].to;if(yfa||yson[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]]) yfa[top[y]];else xfa[top[x]];if(dep[x]dep[y]) return x;return y;
}
void ins(int x)
{if(!cnt){s[cnt]x;return;}int lcaLCA(s[cnt],x);while(cnt1dep[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 ils[x];i;ia[i].next){int ya[i].to;dp(y);if(siz[y]){siz[y]0;ans;}}}else{for(int ils[x];i;ia[i].next){int ya[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 i1;in;i){int x,y;scanf(%d%d,x,y);adde(x,y);adde(y,x);}dfs1(1);top[1]1;dfs2(1,1);tot0;memset(siz,0,sizeof(siz));memset(ls,0,sizeof(ls));scanf(%d,q);while(q--){int k;cnt0;ans0;scanf(%d,k);p[0]1;for(int i1;ik;i){scanf(%d,p[i]);siz[p[i]];}for(int i1;ik;i)if(siz[fa[p[i]]]){puts(-1);p[0]0;break;}if(!p[0]){for(int i1;ik;i)siz[p[i]]--;continue;}sort(p1,p1k,cmp);if(p[1]!1) s[cnt]1;for(int i1;ik;i) ins(p[i]);while(cnt1) adde(s[cnt-1],s[cnt]),cnt--;dp(1);siz[1]tot0;printf(%d\n,ans);}
}
