題意;

一棵大小為n的有根樹,根為1,有q次查詢,每次查詢給定一個set,set里的點為不重要點,不在set里的點為重要點,問樹上有多少個點滿足一下兩個條件

1.是重要的點.

2.是兩個重要的點的最近公共祖先

解題思路:

這題的結(jié)題方法比較巧.考慮一個不是重要的點能滿足條件,需要它有兩個子樹存在重要的點,如果我們從不是重要的點里深度最深的點開始考慮,如果這個點有兩個子樹,那么就一定符合要求,如果沒有兒子的話,那么以這個點的整棵子樹就不存在重要的點,它對與父親的存在重要點的子樹數(shù)量的恭喜就不存在,所以可以把它父親的兒子-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]);     }   }  }