# [Codeforces613D]Kingdom and its Cities（虚树，树型动态规划）

### Description

Meanwhile, the kingdom of K is getting ready for the marriage of the King's daughter. However, in order not to lose face in front of the relatives, the King should first finish reforms in his kingdom. As the King can not wait for his daughter's marriage, reforms must be finished as soon as possible.
The kingdom currently consists of n cities. Cities are connected by n - 1 bidirectional road, such that one can get from any city to any other city. As the King had to save a lot, there is only one path between any two cities.
What is the point of the reform? The key ministries of the state should be relocated to distinct cities (we call such cities important). However, due to the fact that there is a high risk of an attack by barbarians it must be done carefully. The King has made several plans, each of which is described by a set of important cities, and now wonders what is the best plan.
Barbarians can capture some of the cities that are not important (the important ones will have enough protection for sure), after that the captured city becomes impassable. In particular, an interesting feature of the plan is the minimum number of cities that the barbarians need to capture in order to make all the important cities isolated, that is, from all important cities it would be impossible to reach any other important city.
Help the King to calculate this characteristic for each of his plan.

## 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101000;
const int maxM=maxN*2;
const int maxBit=20;
const int inf=2147483647;

int n;
int Fa[maxBit][maxN],Depth[maxN];
int dfncnt=0,Dfn[maxN],Last[maxN];
int Node[maxN<<1],Stack[maxN<<1],Mark[maxN],Size[maxN];

void dfs_init(int u,int fa);
int GetLCA(int u,int v);
bool cmp(int a,int b);
int dfs(int u,int fa);

int main()
{
scanf("%d",&n);
for (int i=1;i<n;i++)
{
int u,v;scanf("%d%d",&u,&v);
}
dfs_init(1,0);
for (int i=1;i<maxBit;i++)
for (int j=1;j<=n;j++)
if ((Fa[i-1][j])&&(Fa[i-1][Fa[i-1][j]]))
Fa[i][j]=Fa[i-1][Fa[i-1][j]];

int TTT;scanf("%d",&TTT);
while (TTT--)
{
int K;scanf("%d",&K);
for (int i=1;i<=K;i++) scanf("%d",&Node[i]);
for (int i=1;i<=K;i++) Mark[Node[i]]=1;

bool flag=1;
for (int i=1;i<=K;i++)
if (Mark[Fa[0][Node[i]]]){
flag=0;break;
}
if (flag==0)
{
printf("-1\n");
for (int i=1;i<=K;i++) Mark[Node[i]]=0;
continue;
}

sort(&Node[1],&Node[K+1],cmp);
for (int i=1;i<K;i++) Node[K+i]=GetLCA(Node[i],Node[i+1]);
K=K+K;Node[K]=1;
sort(&Node[1],&Node[K+1],cmp);K=unique(&Node[1],&Node[K+1])-Node-1;

edgecnt=0;

int top=0;
for (int i=1;i<=K;i++)
{
while ((top)&&(Last[Stack[top]]<Dfn[Node[i]])) top--;
Stack[++top]=Node[i];
}

printf("%d\n",dfs(1,0));

for (int i=1;i<=K;i++) Mark[Node[i]]=0;
}
return 0;
}

{
return;
}

void dfs_init(int u,int fa)
{
Depth[u]=Depth[fa]+1;
Dfn[u]=++dfncnt;
if (V[i]!=fa)
{
Fa[0][V[i]]=u;
dfs_init(V[i],u);
}
Last[u]=dfncnt;return;
}

int GetLCA(int u,int v)
{
if (Depth[u]<Depth[v]) swap(u,v);
for (int i=maxBit-1;i>=0;i--) if ((Fa[i][u])&&(Depth[Fa[i][u]]>=Depth[v])) u=Fa[i][u];
if (u==v) return u;
for (int i=maxBit-1;i>=0;i--) if ((Fa[i][u])&&(Fa[i][v])&&(Fa[i][u]!=Fa[i][v])) u=Fa[i][u],v=Fa[i][v];
return Fa[0][u];
}

bool cmp(int a,int b)
{
return Dfn[a]<Dfn[b];
}

int dfs(int u,int fa)
{
int ret=0,cnt=0;
if (V[i]!=fa)
{
ret+=dfs(V[i],u);
cnt+=Size[V[i]];
}
if (Mark[u])
{
Size[u]=1;
ret+=cnt;
}
else
{
ret+=(cnt>1);
Size[u]=(cnt==1);
}
return ret;
}


HNCJ OIer 一枚