CF613D

题意：

一个王国有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号点加入栈中。

void insert(int x)
{
    if(top==0)
    {
        sta[top=1]=x;
        return;
    }
    int l=lca(x,sta[top]);
    if(l==sta[top])
    {
        sta[++top]=x;
        return;
    }
    while(top>1 && dep[sta[top-1]]>=dep[l])
    {
        addage(sta[top],sta[top-1],ee,headd,jss);
        addage(sta[top-1],sta[top],ee,headd,jss);
        --top;
    }
    if(l!=sta[top])
    {
        addage(sta[top],l,ee,headd,jss);
        addage(l,sta[top],ee,headd,jss);
        sta[top]=l;
    }
    sta[++top]=x;
}
void build()
{
    jss=0;
    memset(headd,0,sizeof headd);
    if(pt[1]!=1)sta[top=1]=1;
    for(int i=1;i<=m;++i)
        insert(pt[i]);
    while(top>1)
    {
        addage(sta[top],sta[top-1],ee,headd,jss);
        addage(sta[top-1],sta[top],ee,headd,jss);
        --top;
    }
}

————————————————————————————————————————

  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
",ff[1]);
135     }
136     return 0;
137 }

View Code