圆方树入门

Posted on   |   In , ,

前言

刚仙人掌入门….

对于一类点双问题 我们可以采用圆方树解决

大致做法就是点双缩环 变成树形结构 从而解决树形问题

例题

P4630 APIO2018 铁人两项

题意:

统计有多少个三元组$(s,c,f)$ 满足从$s->c$和$c->f$的路径不相交

题解:

首先我们可以确定的是 在同一个点双分量内的两个点$s,v$必然可以从这个点双分量找到第三个点$w$( $w!=s$并且$w!=v$)

那么问题转化成 对于任意两点 第三个点可以是这两点的任意路径中除去头尾的节点的并集

那用点双缩环 圆点的价值是-1 方点的价值是点双规模的大小

对于任意两点的答案就是圆方树路径的求和

我们考虑树形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
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
// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=4e5+10;
const double eps=1e-8;
const int mod=1e9+9;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}


int n,m;
typedef struct node{
    int x,y;
}node;
node d[MAXN];
int dfn[MAXN],low[MAXN],bcc_pos[MAXN];
int num,cnt,st[MAXN],tot;
ll a[MAXN];
vector<int>vec[MAXN],p[MAXN];
void tarjan_Bcc(int x,int pre){
    dfn[x]=low[x]=++cnt;
    link(x){
    if(dfn[j->t]&&dfn[j->t]<dfn[x]&&j->t!=pre){
        st[++tot]=j->v;
        low[x]=min(low[x],dfn[j->t]);
    }
    else if(!dfn[j->t]){
        st[++tot]=j->v;
        tarjan_Bcc(j->t,x);
        low[x]=min(low[x],low[j->t]);
        if(low[j->t]>=dfn[x]){
        num++;
        while(1){
            int y=st[tot--];
            if(bcc_pos[d[y].x]!=num){
            bcc_pos[d[y].x]=num;
            p[num-n].pb(d[y].x);
            }
            if(bcc_pos[d[y].y]!=num){
            bcc_pos[d[y].y]=num;
            p[num-n].pb(d[y].y);
            }
            if(y==j->v)break;
        }
        a[num]=p[num-n].size();
        for(int i=0;i<p[num-n].size();i++){
            vec[num].pb(p[num-n][i]);
            vec[p[num-n][i]].pb(num);
        }
        }
    }
    }
}
ll ans;
ll sum[MAXN],size[MAXN];
void dfs(int x,int pre){
    sum[x]=0;size[x]=0;bool flag=0;
    //cout<<x<<":::"<<pre<<endl;
    for(int i=0;i<vec[x].size();i++){
    if(vec[x][i]==pre)continue;
    dfs(vec[x][i],x);
    //cout<<x<<"::::==="<<vec[x][i]<<endl;
    if(!flag)sum[x]+=sum[vec[x][i]],size[x]+=size[vec[x][i]],flag=1;
    else{
        ans+=(size[x]*sum[vec[x][i]]+size[vec[x][i]]*sum[x]+a[x]*size[x]*size[vec[x][i]]);
        sum[x]+=sum[vec[x][i]];size[x]+=size[vec[x][i]];
    }
    }
    if(x<=n){
    ans+=(sum[x]+1ll*a[x]*size[x]);
    size[x]++;
    sum[x]+=1ll*size[x]*a[x];
    }
    else{
    sum[x]+=1ll*size[x]*a[x];
    }
}
int main(){
    n=read();m=read();
    inc(i,1,n)a[i]=-1;
    inc(i,1,m)d[i].x=read(),d[i].y=read(),add(d[i].x,d[i].y,i),add(d[i].y,d[i].x,i);
    num=n;
    inc(i,1,n)if(!dfn[i])tarjan_Bcc(i,0),dfs(i,0);
    printf("%lld\n",ans*2);
    return 0;
}

P4606 SDOI2018 战略游戏

题意:

给定一个$n$个点,$m$条边的无向图,$q$次询问,每次询问$k$个点,表示这$k$个点已经被小C占领,如果你能找到一个点(未被占领)去除这个点以及其连边后,使得小C存在一对节点$<u,v>$不连通,则小Q获胜,问能让小Q获胜的节点有多少个

题解:

很显然的 如果在一个点双分量里面 则去除任何一个点都不会影响其他节点的连通性

那么对于任意两个点双分量 我们只有去除这两个点双分量路径上的割点 才会影响这两个点双分量的连通性

所以我们用点双缩点后 对于割点的权值为1 非割点价值为0

然后对于$k$个关键节点 在圆方树上做出虚树 对于每个点考虑是否是在点双分量的路径上即可

代码实现:

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
const int mod=1e9+9;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int _,n,m;
typedef struct node{
    int x,y;
}node;
node que[MAXN];
vector<int>vec[MAXN],p[MAXN];
int bcc_pos[MAXN],num,cnt;
int a[MAXN],st[MAXN],tot,dfn[MAXN],low[MAXN];
void tarjan_Bcc(int x,int pre){
    dfn[x]=low[x]=++cnt;
    int ch=0;
    link(x){
	if(dfn[j->t]&&dfn[j->t]<dfn[x]&&j->t!=pre){
	    low[x]=min(low[x],dfn[j->t]);
	    st[++tot]=j->v;
	}
	else if(!dfn[j->t]){
	    ch++;
	    st[++tot]=j->v;
	    tarjan_Bcc(j->t,x);
	    low[x]=min(low[j->t],low[x]);
	    if(low[j->t]>=dfn[x]){
		a[x]=1;num++;p[num-n].clear();
		while(1){
		    int y=st[tot--];
		    if(bcc_pos[que[y].x]!=num){
			bcc_pos[que[y].x]=num;
			p[num-n].pb(que[y].x);
		    }
		    if(bcc_pos[que[y].y]!=num){
			bcc_pos[que[y].y]=num;
			p[num-n].pb(que[y].y);
		    }
		    if(y==j->v)break;
		}
		for(int i=0;i<p[num-n].size();i++){
		    vec[num].pb(p[num-n][i]);
		    vec[p[num-n][i]].pb(num);
		}
	    }
	}
    }
    if(pre==0&&ch>=2)a[x]=1;
    else if(pre==0)a[x]=0;
}
int dep[MAXN],fa[MAXN],sum[MAXN],son[MAXN],Num[MAXN],P[MAXN],cnt1;
void dfs(int x,int pre,int deep){
    fa[x]=pre;dep[x]=deep+1;Num[x]=1;P[x]=++cnt1;
    sum[x]=sum[pre]+a[x];
    for(int i=0;i<vec[x].size();i++){
	if(vec[x][i]==pre)continue;
	dfs(vec[x][i],x,deep+1);
	Num[x]+=Num[vec[x][i]];
	if(son[x]==-1||Num[son[x]]<Num[vec[x][i]])son[x]=vec[x][i];
    }
}
int tp[MAXN];
void _dfs(int x,int td){
    tp[x]=td;
    if(son[x]!=-1)_dfs(son[x],td);
    for(int i=0;i<vec[x].size();i++)if(vec[x][i]!=fa[x]&&vec[x][i]!=son[x])_dfs(vec[x][i],vec[x][i]);
}
int Lca(int x,int y){
    int xx=tp[x];int yy=tp[y];
    while(xx!=yy){
	if(dep[xx]<dep[yy])swap(xx,yy),swap(x,y);
	x=fa[xx];xx=tp[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
vector<int>v1[MAXN],v2,v3;
int K,calc[MAXN],ans;
bool cmp(int x,int y){return P[x]<P[y];}
void built(int x){
    if(!tot){st[++tot]=x;v3.pb(x);return ;}
    int lca=Lca(st[tot],x);
    while(tot>1&&dep[lca]<dep[st[tot-1]]){
	v1[st[tot]].pb(st[tot-1]);
	v1[st[tot-1]].pb(st[tot]);
	tot--;
    }
    if(tot&&dep[lca]<dep[st[tot]]){
	v1[lca].pb(st[tot]);
	v1[st[tot]].pb(lca);
	tot--;
    }
    if(!tot||dep[st[tot]]<dep[lca])st[++tot]=lca,v3.pb(lca);
    st[++tot]=x;v3.pb(x);
}
void __dfs(int x,int pre){
    bool flag=0;
    for(int i=0;i<v1[x].size();i++){
	if(v1[x][i]==pre)continue;
	__dfs(v1[x][i],x);
	calc[x]+=calc[v1[x][i]];
	if(calc[v1[x][i]]&&calc[v1[x][i]]<K)flag=1;
    }
    if(flag)ans+=a[x];
    if(calc[x]!=K){
	if(!flag)ans+=a[x];
	ans+=(sum[x]-sum[pre]-a[x]);
    }
}
int main(){
    _=read();
    while(_--){
	memset(h,0,sizeof(h));o=e;
	n=read();m=read();
	int x,y;
	inc(i,1,m)que[i].x=read(),que[i].y=read(),add(que[i].x,que[i].y,i),add(que[i].y,que[i].x,i);
	tot=cnt=0;num=n;
	tarjan_Bcc(1,0);cnt1=0;
	inc(i,1,num)son[i]=-1;
	dfs(1,0,0);_dfs(1,1);
	int q=read();
	while(q--){
	    K=read();v2.clear();v3.clear();
	    inc(i,1,K)x=read(),v2.pb(x),calc[x]=1;
	    sort(v2.begin(),v2.end(),cmp);
	    tot=0;
	    inc(i,1,K)built(v2[i-1]);
	    while(tot>1){v1[st[tot]].pb(st[tot-1]);v1[st[tot-1]].pb(st[tot]);tot--;}
	    if(st[1]!=1){v1[1].pb(st[1]);v1[st[1]].pb(1);v3.pb(1);}
	    ans=0;__dfs(1,0);
	    for(int i=0;i<v3.size();i++)v1[v3[i]].clear(),calc[v3[i]]=0;
	    inc(i,1,K)if(a[v2[i-1]])ans--;
	    printf("%d\n",ans);
	}
	inc(i,1,num)vec[i].clear(),bcc_pos[i]=low[i]=dfn[i]=0,a[i]=0;
    }
    return 0;
}