2019, XII Samara Regional Intercollegiate Programming Contest

2019, XII Samara Regional Intercollegiate Programming Contest

十月 15, 2020

D. Country Division

  • 题意

给出一个n(n<2e5)个点n-1条边的树

q组询问

每次将一些点染红,一些点染蓝

问是否能删掉一条边使得红点相互联通,蓝点相互联通,但红蓝点不能相互联通

  • 题解

参考博客

这题当作树上倍增寻找Lca算法的练习题记录

我们求出所有红点LcaRed，所有蓝点LcaBlue，如果所有蓝点不在LcaRed的子树中或者

所有红点不在LcaBlue的子树中，那么就是yes。

这里有几个技巧：

  • 我们不选择两两点找公共祖先,而是直接找dfs序最小的点(即dfs最先遍历到的点)

    和dfs序最大的点(即dfs最后遍历到的点)的最近公共祖先

    那两个点的公共祖先就是所有红点/蓝点的最近公共祖先

  • 如何判断一些点是否为一个点的子孙结点？

    记录每个点的Dfsin和Dfsout [Dfsin,Dfsout]表示该点的所有子孙节点对应的dfs序

​

  • 那么由于根节点选择的不同是否对判断结果产生影响？事实是不会

    若红点连通块和蓝点连通块联通 那么无论以哪个点作为根节点

    必然都不符合条件(如果所有蓝点不在LcaRed的子树中或者所有红点不在LcaBlue的子树中)

    反之若以某点为根节点时符合条件(如果所有蓝点不在LcaRed的子树中或者所有红点不在LcaBlue的子树中)

    那么任意其他点为根节点时也符合条件

    不会证明但是画图大概能感觉到 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int Max=2e5+5;
const ll Mod=1e9+7;
//bool vis[(int)1e7+5];
/*

*/
vector<int>mp[Max];
int cnt=0;
///Dfsin/Dfsout 每个点的区间[Dfsin,Dfsout]以内的数
///表示该点的所有子节点对应的dfs序
int Dfsin[Max],Dfsout[Max];
int Fa[Max][20],deep[Max];
int Lca(int x,int y){
    if(deep[x]<deep[y])swap(x,y);
    ///x的深度比y深
    ///找到高度恰好大于等于y高度的x的祖先
    for(int i=19;i>=0;i--){
        if(deep[Fa[x][i]]>=deep[y])x=Fa[x][i];
    }
    if(x==y)return x;
    ///若Fa[x][i]==Fa[y][i]则该点为它们的公共祖先
    ///但是不是最近的公共祖先
    ///若Fa[x][i]!=Fa[y][i]则上跳,二进制一定能表示出一个确定的公共点
    for(int i=19;i>=0;i--){
        if(Fa[x][i]!=Fa[y][i]){
            x=Fa[x][i];
            y=Fa[y][i];
        }
    }
    ///最后更新到的点就是两者的LCA
    return Fa[x][0];
}
void dfs(int now,int fa){
    Dfsin[now]=++cnt;
    deep[now]=deep[fa]+1;
    Fa[now][0]=fa;
    for(int i=1;i<20;i++)Fa[now][i]=Fa[Fa[now][i-1]][i-1];
    for(auto to:mp[now]){
        if(to==fa)continue;
        dfs(to,now);
    }
    Dfsout[now]=cnt;
}
bool check(int u,vector<int> node){
    for(auto i:node){
        if(Dfsin[u]<=Dfsin[i]&&Dfsout[u]>=Dfsout[i])return 0;
    }
    return 1;
}
int main(){
    //Turnoff;
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    dfs(1,0);
    int q;cin>>q;
    while(q--){
        int r,b;cin>>r>>b;
        vector<int>Red,Blue;
        int Firstvis=0,Lastvis=0;
        for(int i=0;i<r;i++){
            int temp;cin>>temp;
            Red.push_back(temp);
            if(!Firstvis||Dfsin[Firstvis]>Dfsin[temp])Firstvis=temp;
            if(!Lastvis||Dfsin[Lastvis]<Dfsin[temp])Lastvis=temp;
        }
        int LcaRed=Lca(Lastvis,Firstvis);
        Lastvis=0,Firstvis=0;
        for(int i=0;i<b;i++){
            int temp;cin>>temp;
            Blue.push_back(temp);
            if(!Firstvis||Dfsin[Firstvis]>Dfsin[temp])Firstvis=temp;
            if(!Lastvis||Dfsin[Lastvis]<Dfsin[temp])Lastvis=temp;
        }
        int LcaBlue=Lca(Lastvis,Firstvis);
        if(check(LcaBlue,Red))cout<<"YES"<<endl;
        else if(check(LcaRed,Blue))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}