题意：
一个王国有n座城市，城市之间由n-1条道路相连，形成一个树结构，国王决定将一些城市设为重要城市。
这个国家有的时候会遭受外敌入侵，重要城市由于加强了防护，一定不会被占领。而非重要城市一旦被占领，这座城市就不能通行。
国王定了若干选择重要城市的计划，他想知道，对于每个计划，外敌至少要占领多少个非重要城市，才会导致重要城市之间两两不连通。如果外敌无论如何都不可能导致这种局面，输出-1
————————————————————————————————————————
首先，在洛谷交的，有一个点没有过。CF，外语网站而且很慢，不试了！
建立虚树，然后在虚树上面树形DP。
虚树，就是在做树形DP时，我们经常发现有许多点根本没用，比如这个题目中的非重要城市。我们可以把重要节点和他们的连接点（LCA）取出来重新建一棵树，这就是虚树。
方法：
首先，dfs，求出dfs序:DFN，并求出每个点的深度dep[]和LCA辅助数组f[][]
void dfs(int u,int fa)
{
f[u][0]=fa;
for(int i=1;i<20 && f[u][i-1]!=0;++i)f[u][i]=f[f[u][i-1]][i-1];
dfn[u]=++tim;dep[u]=dep[fa]+1;
for(int i=head[u];i;i=e[i].nxt)
if(e[i].v!=fa)dfs(e[i].v,u);
}
然后，对于所有的重要节点进行记录(pt[])并打标记(ispt[])
下面，将重要节点（pt[]）按照DFN[]进行排序
最后，我们将pt[]中的重要节点一次取出建立虚树。
建立的虚树采用增量的方法：
把取出的点一次加入到栈里面，从栈底到栈顶的重要节点可以连成一条从根方向到叶子方向的链。
当加入当前点u时，如果栈中没用其它的点则可以直接加入点u
如果u点与栈顶的点的lca是栈顶点，则可以直接将u点加入，这样栈中的点形成一条更长的链
如果栈顶点和u点的lca不是栈顶点，那么也就是u点和栈顶点处于原树中不同的分支。我们比lca更深（比较dep[]）的点依次弹出，并把相邻的点建边（这就是虚树的一部分）。然后把判断lca是否在栈中，如果不在就需要把lca加入栈中，然后把u点加入栈中。
这样所有的点都加入完成后，最后还剩余了栈中的一条链，把栈中的点一次出栈并建边，虚树完成。
注：为了有一个总的根，所以通常把1号点加入栈中。
————————————————————————————————————————
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1e5+10;
4 int n,q;
5 struct edge
6 {
7 int u,v,nxt;
8 }e[maxn],ee[maxn];
9 int head[maxn],headd[maxn],js,jss;
10 void addage(int u,int v,edge e[],int head[],int &js)
11 {
12 e[++js].u=u;e[js].v=v;
13 e[js].nxt=head[u];head[u]=js;
14 }
15 int dfn[maxn],tim,f[maxn][20],dep[maxn];
16 void dfs(int u,int fa)
17 {
18 f[u][0]=fa;
19 for(int i=1;i<20 && f[u][i-1]!=0;++i)f[u][i]=f[f[u][i-1]][i-1];
20 dfn[u]=++tim;dep[u]=dep[fa]+1;
21 for(int i=head[u];i;i=e[i].nxt)
22 if(e[i].v!=fa)dfs(e[i].v,u);
23 }
24 int pt[maxn],m,sta[maxn],top;
25 bool ispt[maxn];
26 bool cmp(int a,int b)
27 {
28 return dfn[a]<dfn[b];
29 }
30 int lca(int u,int v)
31 {
32 if(dep[v]>dep[u])swap(u,v);
33 for(int i=19;i>=0;--i)
34 if(dep[f[u][i]]>=dep[v])u=f[u][i];
35 if(u==v)return u;
36 for(int i=19;i>=0;--i)
37 if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
38 return f[u][0];
39 }
40 void insert(int x)
41 {
42 if(top==0)
43 {
44 sta[top=1]=x;
45 return;
46 }
47 int l=lca(x,sta[top]);
48 if(l==sta[top])
49 {
50 sta[++top]=x;
51 return;
52 }
53 while(top>1 && dep[sta[top-1]]>=dep[l])
54 {
55 addage(sta[top],sta[top-1],ee,headd,jss);
56 addage(sta[top-1],sta[top],ee,headd,jss);
57 --top;
58 }
59 if(l!=sta[top])
60 {
61 addage(sta[top],l,ee,headd,jss);
62 addage(l,sta[top],ee,headd,jss);
63 sta[top]=l;
64 }
65 sta[++top]=x;
66 }
67 void build()
68 {
69 jss=0;
70 memset(headd,0,sizeof headd);
71 if(pt[1]!=1)sta[top=1]=1;
72 for(int i=1;i<=m;++i)
73 insert(pt[i]);
74 while(top>1)
75 {
76 addage(sta[top],sta[top-1],ee,headd,jss);
77 addage(sta[top-1],sta[top],ee,headd,jss);
78 --top;
79 }
80 }
81 int ff[maxn],g[maxn];
82 void dp(int u,int fa)
83 {
84 ff[u]=g[u]=0;
85 for(int i=head[u];i;i=e[i].nxt)
86 {
87 int v=e[i].v;
88 if(v==fa)continue;
89 dp(v,u);
90 ff[u]+=ff[v];g[u]+=g[v];
91 }
92 if(!ispt[u])
93 {
94 ff[u]+=(g[u]>1);
95 g[u]=(g[u]==1);
96 }
97 else
98 {
99 ff[u]+=g[u];
100 g[u]=1;
101 }
102 }
103 int main()
104 {
105 scanf("%d",&n);
106 for(int u,v,i=1;i<n;++i)
107 {
108 scanf("%d%d",&u,&v);
109 addage(u,v,e,head,js);addage(v,u,e,head,js);
110 }
111 dfs(1,0);
112 scanf("%d",&q);
113 while(q--)
114 {
115 scanf("%d",&m);
116 memset(pt,0,sizeof pt);
117 memset(ispt,0,sizeof ispt);
118 for(int i=1;i<=m;++i)
119 {
120 scanf("%d",pt+i);
121 ispt[pt[i]]=1;
122 }
123 sort(pt+1,pt+m,cmp);
124 bool flag=1;
125 for(int i=1;i<=m;++i)
126 if(ispt[f[pt[i]][0]])flag=0;
127 if(!flag)
128 {
129 puts("-1");
130 continue;
131 }
132 build();
133 dp(1,0);
134 printf("%d\n",ff[1]);
135 }
136 return 0;
137 }
View Code