https://codeforces.com/problemset/problem/613/D
题目大意:有n个点,每次询问要最少移除多少个点使得关键点分隔
思路:首先,如果关键点是相连的话,那么一定是不行的。
然后因为询问的总节点数不多,可以使用虚数。
我们按照关键节点建立虚数后进行树形dp;
在虚数中,
如果u是关键节点,那么如果儿子v也有关键节点的性质则在连边的中间必须去移除一个点。
如果不是关键节点,如果儿子中有超过1个关键节点的话,那么该节点必须移除。
如果儿子中只有一个关键节点的话,那么该节点将会继承儿子的关键节点的性质。
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <cstdlib>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(a) ((a)&-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i=0;(i)<(n);i++)
#define rep1(i,n) for(int i=1;(i)<=(n);i++)
#define se second
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define ac cout<<ans<<"\n"
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1};
const ll mod=1e9+7;
const ll N =250007;
const ll M =250000;
const double eps = 1e-4;
//const double pi=acos(-1);
ll qk(ll a,ll b){ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b/=2;}return ans%mod;}
int n;
int cnt,m;
int ldfn[N],rdfn[N];//当前节点的dfs序
int fa[N][20];//f[i][j]表示i节点向上2^j步的祖先
int dep[N];//节点深度
int stk[N];//栈,用于构建虚树
int d[N<<1];//用于存储虚树的节点编号。由于LCA可能有重复,因此需要开2倍
int vis[N];//标记当前节点是否为关键点
vector<int> RG[N];
vector<int> VG[N];
void predfs(int u,int f,int depth)
{
ldfn[u]=++cnt;
dep[u]=depth;
fa[u][0]=f;
for(int j=1;j<20;j++)
{
fa[u][j]=fa[fa[u][j-1]][j-1];
}
for(int v:RG[u])
{
if(v==f) continue;
predfs(v,u,depth+1);
}
rdfn[u]=cnt;
}
int lca(int u,int v)
{
if(dep[u]<dep[v])
swap(u,v);
int delta=dep[u]-dep[v];
for(int j=0;j<20&δj++)
{
if(delta&(1<<j))
u=fa[u][j];
}
if(u==v) return u;
for(int j=20-1;j>=0;j--)
{
if(fa[u][j]!=fa[v][j])
{
u=fa[u][j];
v=fa[v][j];
}
}
return fa[u][0];
}
bool cmp(int x,int y)
{
return ldfn[x]<ldfn[y];
}
void build()
{
sort(d+1,d+m+1,cmp);
int keynum=m;
for(int i=1;i<keynum;i++) d[++m]=lca(d[i],d[i+1]);
sort(d+1,d+m+1,cmp);
m=unique(d+1,d+m+1)-d-1;
int top=0;
stk[++top]=d[1];
for(int i=2;i<=m;i++)
{
while(top&&rdfn[stk[top]]<ldfn[d[i]])
top--;
if(top)
VG[stk[top]].push_back(d[i]);
stk[++top]=d[i];
}
}
int ans[N];
int son[N];
void dfs(int u,int f){
ans[u]=0;
if(vis[u]){
son[u]=1;
for(int v:VG[u]){
if(v==f) continue;
dfs(v,u);
ans[u]+=ans[v];
if(son[v]>0) ans[u]++;
}
}else{
son[u]=0;
for(int v:VG[u]){
if(v==f) continue;
dfs(v,u);
ans[u]+=ans[v];
son[u]+=son[v];
}
if(son[u]>1){
son[u]=0;
ans[u]++;
}
}
VG[u].clear();
}
void sovle(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
RG[u].pb(v);
RG[v].pb(u);
}
predfs(1,0,0);
int q;
cin>>q;
to:while(q--){
cin>>m;
for(int i=1;i<=m;i++){
cin>>d[i];
vis[d[i]]=1;
}
for(int i=1;i<=m;i++){
if(vis[fa[d[i]][0]]){
cout<<-1<<endl;
for(int i=1;i<=m;i++) vis[d[i]]=0;
goto to;
}
}
build();
dfs(d[1],0);
cout<<ans[d[1]]<<endl;
for(int i=1;i<=m;i++) vis[d[i]]=0;
}
}
int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#else
// ios
int t=1;
// cin>>t;
while(t--) sovle();
#endif // LOCAL
return 0;
}