Given a rooted tree with n vertices, some of the vertices are important.
An auxiliary set is a set containing vertices satisfying at least one of the two conditions：
∙
∙It is an important vertex
∙
∙It is the least common ancestor of two different important vertices.
You are given a tree with n vertices (1 is the root) and q queries.
Each query is a set of nodes which indicates the
unimportant vertices in the tree. Answer the size (i.e. number of vertices) of the auxiliary set for each query.
Input
T≤1000
T≤1000), which indicates the number of test cases.
For each test case, the first line contains two integers n (
1≤n≤100000
1≤n≤100000), q (
0≤q≤100000
0≤q≤100000).
In the following n -1 lines, the i-th line contains two integers
ui,vi(1≤ui,vi≤n)
ui,vi(1≤ui,vi≤n)indicating there is an edge between
ui
uii and
vi
vi in the tree.
In the next q lines, the i-th line first comes with an integer
mi(1≤mi≤100000)
mi(1≤mi≤100000)indicating the number of vertices in the query set.Then comes with mi different integers, indicating the nodes in the query set.
It is guaranteed that
∑qi=1mi≤100000
∑i=1qmi≤100000.
It is also guaranteed that the number of test cases in which
n≥1000
n≥1000 or
∑qi=1mi≥1000
∑i=1qmi≥1000 is no more than 10.
Output
For each test case, first output one line "Case #x:", where x is the case number (starting from 1).
Then q lines follow, i-th line contains an integer indicating the size of the auxiliary set for each query.
Sample Input
1
6 3
6 4
2 5
5 4
1 5
5 3
3 1 2 3
1 5
3 3 1 4 Sample Output
Case #1:
3
6
3 #include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int low(int x) { return x&-x; }
int T, n, m, x, y;
int ft[N],nt[N],u[N],sz;
int L[N], R[N], t;
int f[N],dep[N],a[N],b[N], fa[N], cnt[N];
int sum(int x) {
int res = 0;
for (int i = x;i;i-=low(i)) {
res+=f[i];
}
return res;
}
void add(int x,int y) {
for (int i = x;i<=n;i+=low(i)) f[i]+=y;
}
void dfs(int x,int y){
dep[x] = dep[y] + 1;
fa[x] = y;
L[x] = ++t;
cnt[x] = 0;
add(L[x], 1);
for (int i = ft[x];~i;i=nt[i]) {
if (u[i] == y) continue;
dfs(u[i], x);
cnt[x]++;
}
R[x] = t;
}
bool cmp(int x,int y) {
return dep[x]>dep[y];
}
int main(){
int cas = 1;
for (scanf("%d",&T);T--;cas++) {
scanf("%d%d",&n, &m);
sz = t = f[n] = dep[0] = 0;
for (int i = 1;i <= n;i++) ft[i] = -1;
for (int i = 1;i < n;i++) {
scanf("%d%d",&x,&y);
f[i] = 0;
u[sz] = y; nt[sz] = ft[x]; ft[x] = sz++;
u[sz] = x; nt[sz] = ft[y]; ft[y] = sz++;
}
dfs(1,0);
printf("Case #%d:\n",cas);
while (m--) {
scanf("%d",&x);
for (int i = 0;i<x;i++) {
scanf("%d",&a[i]);
}
sort(a,a+x,cmp);
int ans = n - x;
for (int i = 0;i<x;i++) {
add(L[a[i]],-1);
if (cnt[a[i]] > 1) ans++;
b[i] = 0;
if (sum(R[a[i]]) - sum(L[a[i]] - 1) == 0) {
cnt[fa[a[i]]]--; b[i] = 1;
}
}
printf("%d\n",ans);
for (int i = 0;i<x;i++) {
add(L[a[i]],1);
if (b[i]) {
cnt[fa[a[i]]]++;
}
}
}
}
return 0;
}