本文主要是介绍Auxiliary Set HDU - 5927，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
看了题解才会... 之前还一直想用LCA怎么搞...
对于一个非重要点 只要其下至少两颗子树上分别有两个重要点 那这个非重要点一定是他们的LCA 也变成了重要节点
dfs一遍 记录每个节点的直接孩子有几个 记为son[cur] 对于每一个查询 把点按深度从深到浅排序 然后扫一遍
如果当前点的son[cur]==0 那么以当前点为根的子树上已经不存在重要点 其父节点也就少了一个提供重要点的来源 son[fa[cur]]--
如果当前点的son[cur]==1 对自己对父节点都没啥影响 忽略
如果当前点的son[cur]==2 那么他也会被记为重要点
#include <bits/stdc++.h>
using namespace std;struct node1
{int v;int next;
};node1 edge[200010];
int first[100010],fa[100010],son[100010],deep[100010];
int n,num;bool cmp(int u,int v)
{return deep[u]>deep[v];
}void addedge(int u,int v)
{edge[num].v=v;edge[num].next=first[u];first[u]=num++;return;
}void dfs(int cur,int dep)
{int i,v;son[cur]=0,deep[cur]=dep;for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa[cur]){fa[v]=cur,son[cur]++;dfs(v,dep+1);}}return;
}int main()
{int tem[100010],pre[100010];int t,cas,q,k,i,u,v,ans;scanf("%d",&t);for(cas=1;cas<=t;cas++){scanf("%d%d",&n,&q);memset(first,-1,sizeof(first));num=0;for(i=1;i<=n-1;i++){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}fa[1]=-1;dfs(1,1);printf("Case #%d:\n",cas);while(q--){scanf("%d",&k);for(i=1;i<=k;i++){scanf("%d",&pre[i]);tem[pre[i]]=son[pre[i]];}sort(pre+1,pre+k+1,cmp);ans=n-k;for(i=1;i<=k;i++){if(tem[pre[i]]>=2) ans++;else if(tem[pre[i]]==0) tem[fa[pre[i]]]--;}printf("%d\n",ans);}}return 0;
}
如果当前点的son[cur]==1
这篇关于Auxiliary Set HDU - 5927的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
