hdu 5927 Auxiliary Set (dfs)

题意;

一棵大小为n的有根树,根为1,有q次查询,每次查询给定一个set,set里的点为不重要点,不在set里的点为重要点,问树上有多少个点满足一下两个条件

1.是重要的点.

2.是两个重要的点的最近公共祖先

解题思路:

这题的结题方法比较巧.考虑一个不是重要的点能满足条件,需要它有两个子树存在重要的点,如果我们从不是重要的点里深度最深的点开始考虑,如果这个点有两个子树,那么就一定符合要求,如果没有儿子的话,那么以这个点的整棵子树就不存在重要的点,它对与父亲的存在重要点的子树数量的恭喜就不存在,所以可以把它父亲的儿子-1,这样不断往上更新就行.

代码:

#include <bits/stdc++.h>using namespace std;const int maxn=1e5+5;int d[maxn];int book[maxn];vector<int> edg[maxn];int que[maxn];int impor[maxn];int unimpor[maxn];int ans;int son[maxn];int so[maxn];int fa[maxn];bool cmp(int x, int y){    return d[x]>d[y];}void dfs(int x, int y){    fa[x]=y;son[y]++;son[x]=0;d[x]=d[y]+1;    for(int i=0; i<(int)edg[x].size(); i++)    {	    if(edg[x][i]!=y)dfs(edg[x][i],x);    }    return;}int main(){   int t;   cin>>t;   int e=1;    while(t--)   {     int n;     int q;     scanf("%d%d", &n, &q);     int i, j, x, y;         for(i=0; i<n-1; i++)     {	scanf("%d %d", &x, &y); 	edg[x].push_back(y);	edg[y].push_back(x);	     }          dfs(1,0);     int  m;     PRintf("Case #%d:/n", e++);         while(q--)     {	scanf("%d", &m);	for(i=0; i<m; i++)	{  	   scanf("%d", &unimpor[i]);	   so[unimpor[i]]=son[unimpor[i]];	}	ans=n-m;	sort(unimpor, unimpor+m, cmp);	for(i=0; i<m; i++)	{	   if(so[unimpor[i]]>=2)ans++;	   else	   {	    if(so[unimpor[i]]==0)  so[fa[unimpor[i]]]--;	   }	}	printf("%d/n", ans);     }     for(i=1; i<=n; i++)     {     edg[i].clear();//		vector<int>().swap(edg[i]);     }   }  }