虚树复习 CF613 D. Kingdom and its Cities

发表于 更新于 分类于 ， 阅读次数：

许久没写虚树了，找一道复习。

CF613D Kingdom and its Cities

步骤

  1. 在原树上进行dfs，进行LCA预处理，同时得到原树上的dfs序，方便之后虚树构造，此外还可以进行一些dp预处理，便于进行虚树上的第二次dp。
  2. 确定关键节点集合，并按照dfs序排序。
  3. 通过单调栈及LCA算法构建出虚树。
  4. 在虚树上进行树形dp求解。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
sort(h+1,h+k+1,[](const int &x,const int &y){
    return dfn[x]<dfn[y];//按dfs序排序
});
stk[top=1]=h[1];
cnt2=0;//清空存储的前向星
for(int i=2;i<=k;i++)
{
    int now=h[i];
    int lc=lca(now,stk[top]);//最近公共祖先
    //printf("lca(%d,%d)=%d\n",now,stk[top],lc);
    while(top>1&&dfn[lc]<=dfn[stk[top-1]])//情况4,=是情况3
    {//不断将top送入虚树
        adde(stk[top-1],stk[top]);//前向星加边,构建新树
        top--;
    }
    if(dfn[lc]<dfn[stk[top]])//情况2
    {//加边,top出栈,lc和now入栈
        adde(lc,stk[top]);
        stk[top]=lc;
    }//否则为情况1
    stk[++top]=now;
}
while(--top)
    adde(stk[top],stk[top+1]);

思路

直接考虑树形$dp$做法，$dp[x]$表示以$x$为根的子树上的答案。

如果有相邻两个城市为重要节点，那么直接输出$-1$.

否则当前节点为$x$时，若$x$为重要节点，那么$x$需要和其所有包含重要节点的子树断开联系。

如果当前节点不为重要节点，但是有多于一棵子树含有重要节点，那么当前节点被标记占领，$dp[x]=sum_{v\in son(x)}(dp[v])+1$，那么我们发现还需要另外记录某些含有重要节点的子树有没有被“阻断”。而如果$x$只有一个未被阻断的子树，那么可以选择留到后面去阻断。

本来以为建立虚树只是要套模板，没想到还要加上优化，否则清空会被卡成$O(n^2)$的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
const int maxl=30;
vector<int> G[maxn];//无权边,也可以选择链式前向星存图
int gene[maxn][maxl],depth[maxn],lg[maxn],dfn[maxn],tim=0;
void dfs(int x,int fa)
{
    if(!dfn[x])
        dfn[x]=++tim;
    depth[x]=depth[fa]+1;
    gene[x][0]=fa;
    for(int i=1;(1<<i)<=depth[x];i++)//倍增
        gene[x][i]=gene[gene[x][i-1]][i-1];
    for(int i=0;i<G[x].size();i++)
        if(G[x][i]!=fa)
            dfs(G[x][i],x);//在dfs前后加语句可以求出许多有趣的东西
}
int lca(int x,int y)
{
    if(depth[x]<depth[y])//保证x深度≥y
        swap(x,y);
    while(depth[x]>depth[y])//将x提到同一高度
        x=gene[x][lg[depth[x]-depth[y]-1]];
    if(x==y)//是同一个节点
        return x;
    for(int i=lg[depth[x]];i>=0;i--)
        if(gene[x][i]!=gene[y][i])
        {//二分思想,直到跳到LCA的下面一层
            x=gene[x][i];
            y=gene[y][i];
        }
    return gene[x][0];
}
int dist(int x,int y)//x节点到y结点的距离
{
    int tem=lca(x,y);
    return (int)(abs(depth[x]-depth[tem])+abs(depth[y]-depth[tem]));
}
void init(int s,int n)
{
    depth[s]=1;
    for(int i=1;i<=n;i++)//预处理出log2(i)+1的值
        lg[i]=lg[i-1]+((1<<(lg[i-1]+1))==i);//不要写错
    dfs(s,s);
}
int stk[maxn],top;
vector<int>g[maxn];
map<int,bool>vis;
void build(vector<int> &rec,int n)
{
    sort(rec.begin(),rec.end(),[](const int &x,const int &y){
                return dfn[x]<dfn[y];
            });
    stk[top=1]=rec[0];
    g[1].clear();
    auto adde = [](int u,int v)
    {
        g[u].push_back(v);
    };
    for(int i=1;i<rec.size();i++)
    {
        int now=rec[i];
        int lc=lca(now,stk[top]);//最近公共祖先
        while(top>1&&dfn[lc]<=dfn[stk[top-1]])//情况4,=是情况3
        {//不断将top送入虚树
            adde(stk[top-1],stk[top]);//前向星加边,构建新树
            top--;
        }
        if(dfn[lc]<dfn[stk[top]])//情况2
        {//加边,top出栈,lc和now入栈
            g[lc].clear();//奇怪的优化2
            adde(lc,stk[top]);
            stk[top]=lc;
        }//否则为情况1
        g[now].clear();//奇怪的优化
        stk[++top]=now;
    }
    while(--top)
        adde(stk[top],stk[top+1]);
}
int dp[maxn],f[maxn];
void dfs2(int x)
{
    dp[x]=f[x]=0;
    for(int &v:g[x])
    {
        dfs2(v);
        dp[x]+=dp[v];
        f[x]+=f[v];//统计节点与多少重要城市直接相连
    }
    if(vis[x])
    {//重要节点
        dp[x]+=f[x];
        f[x]=1;//本身是重要节点
    }
    else if(f[x]>1)
    {
        dp[x]++;//占领该节点
        f[x]=0;//被阻塞
    }//否则留到以后处理
}
signed main(signed argc, char const *argv[])
{
    int n,u,v,q,k;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    init(1,n);
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&k);
        vector<int>rec;
        vis.clear();
        bool ok=1,ok1=0;
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&u);
            if(u==1)
                ok1=1;
            vis[u]=true;
            rec.push_back(u);
        }
        for(int &x:rec)
            if(x!=1&&vis[gene[x][0]])
            {//父节点也被标记
                ok=0;
                break;
            }
        if(!ok)
        {
            printf("-1\n");
            continue;
        }
        if(!ok1)
            rec.push_back(1);
        build(rec,n);//构建虚树
        dfs2(1);
        printf("%d\n",dp[1]);
    }
    return 0;
}