CF 613 D Kingdom and its Cities 题解

题解"/>

CF 613 D Kingdom and its Cities 题解

CF 613 D Kingdom and its Cities 题解

所用知识虚树&贪心

假设只有一个询问，我们可以如下贪心:

每一个被占领的点的深度要尽可能小！

这是为什么呢？

感性理解一下就是一个占有的点可以分开更多的重要点，会往上传递更少的重要点。

这样我们可以用 d f s dfs dfs来实现。

但是这样的时间复杂度是 O ( n ∗ q ) O(n*q) O(n∗q)的显然不行。

我们可以发现有用的点只有重要的点，和它们两两间的 L C A LCA LCA。所以虚树搞一下就行了。

/*
{By GWj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n;
vector<int> g[100000+20];
int fa[100000+20][18],depth[100000+20],dfn[100000+20],cnt;
void dfs(int now=1,int pre=0,int deep=1){dfn[now]=++cnt;depth[now]=deep;fa[now][0]=pre;rb(i,1,17)fa[now][i]=fa[fa[now][i-1]][i-1];for(int it:g[now]){if(it!=pre)dfs(it,now,deep+1);}
}
int jump(int node,int dis){rl(i,17,0){if((dis>>i)&1) node=fa[node][i];}return node;
}
int lca(int u,int v){if(depth[u]>depth[v]) swap(u,v);v=jump(v,depth[v]-depth[u]);if(u==v) return u;rl(i,17,0){if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}}return fa[v][0];
}
vector<int> vt[100000+20];
vector<int> key_nodes,used;
int imp[100000+20];
bool cmp(int A,int B){return dfn[A]<dfn[B];
}
map<mp,bool> exi;
mp run(int now){for(auto it:vt[now]){if(imp[now]&&imp[it]&&exi.find(II(now,it))!=exi.end()){return II(-1,-1);}}int cnt=0;int rest=0;for(auto it:vt[now]){mp tmp=run(it);rest+=tmp.FIR;cnt+=tmp.SEC;if(tmp.FIR==-1) return II(-1,-1);}if(imp[now]){rest+=cnt;cnt=1;}else{if(cnt>1){cnt=0;rest++;} }return II(rest,cnt);
}
int calc(){sort(ALL(key_nodes),cmp);stack<int> s;s.push(1);used.PB(1);for(auto it:key_nodes){if(it==1) continue;int las=s.top();int llc=lca(las,it);if(llc==las){s.push(it);}else{while(depth[s.top()]>depth[llc]){int z=s.top();s.pop();	if(depth[s.top()]>depth[llc])vt[s.top()].PB(z);else vt[llc].PB(z);}if(s.top()!=llc){used.PB(llc);s.push(llc);}s.push(it);}used.PB(it);}while(!s.empty()){int z=s.top();s.pop();if(!s.empty())vt[s.top()].PB(z);}int rest=run(1).FIR;return rest;
}
int main(){fastio;R(n);rb(i,2,n){int u,v;R2(u,v);g[u].PB(v);g[v].PB(u);exi[II(u,v)]=exi[II(v,u)]=1;}dfs();int q;R(q);while(q--){used.clear();int k;R(k);key_nodes.clear();rb(i,1,k){int key;R(key);imp[key]=1;key_nodes.PB(key);}cout<<calc()<<endl;for(auto it:used){imp[it]=0;vt[it].clear();}}return 0;
}