静态仙人掌

Posted on   |   In , ,

前言

圆方树是一种数据结构 用来解决静态仙人掌问题

这个东西原始的出处应该是paper《Maintaining bridge-connected and biconnected components on-line》

仙人掌的正经定义是: 无向图中每条边至多在一个简单环上

而圆方树是通过点双性质,将简单环处理掉,把一个特殊图变成树形结构,里面的点分为两类圆点(本身图上的点),方点(用来代替点双分量的点)

圆方树有很多性质:

  • 无论如何换根,圆方树的形态不变(因为把环变成了菊花链)
  • 方点和方点不会相连
  • 圆方树的子树 = 原仙人掌的子仙人掌

至于其他的性质,关键在题目中

参照博客:

calabash_boy

zzq

immortalCO

例题

Luogu P4129 [SHOI2006]仙人掌

题目链接: P4120

题意:

判断一个图是否为仙人掌,若为仙人掌则求其支撑子图的个数(支撑子图也是原图的子图，这种子图可以比原来少一些边，但是不能破坏图的连通性，也不能去除原来图上的任何顶点)

题解:

在上一遍已经有了对无向图仙人掌的判定,我们考虑计数,答案为(仙人掌每片叶子的个数+1)的乘积

代码实现:

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#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 int NM=1e6+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;
}
struct Huge{
    static const int MAXN=10001;
    static const int BASE=10000;
    int Num[MAXN];
    int len;
    void init(const string &s){
        memset(Num,0,sizeof(Num));
        int rlen=s.size();
        len=0;
        int i;
        for (i=rlen-5;i>=0;i-=4){
            Num[len]=Num[len]*10+s[i+1]-'0';
            Num[len]=Num[len]*10+s[i+2]-'0';
            Num[len]=Num[len]*10+s[i+3]-'0';
            Num[len]=Num[len]*10+s[i+4]-'0';
            len++;
        }
        if (i<0) i+=4;
        for (int j=0;j<=i;j++)
            Num[len]=Num[len]*10+s[j]-'0';
        len++;
    }
    friend istream& operator>>(istream &i, Huge &v){
        string s;
        i>>s;
        v.init(s);
        return i;
    }
    friend ostream& operator<<(ostream &o, Huge &v){
        if (v.len==0 && v.Num[0]==0){
            o<<'0';
            return o;
        }
        o<<v.Num[v.len-1];
        for (int i=v.len-2;i>=0;i--)
            o<<setw(4)<<setfill('0')<<v.Num[i];
        return o;
    }
    void operator+=(const Huge &v)
    {
        int nlen=max(v.len,len);
        for (int i=0;i<nlen;i++){
            Num[i]+=v.Num[i];
            if (Num[i]>=BASE){
                Num[i]-=BASE;
                Num[i+1]++;
            }
        }
        if (Num[nlen]!=0) nlen++;
        len=nlen;
        //return (*this);
    }
    void operator-=(const Huge &v){
        int nlen=max(v.len,len);
        for (int i=0;i<nlen;i++){
            Num[i]-=v.Num[i];
            if (Num[i]<0){
                Num[i]+=BASE;
                Num[i+1]--;
            }
        }
        while (Num[nlen]==0 && nlen>=0) nlen--;
        len=nlen+1;
        //return (*this);
    }
    void operator*=(const Huge &v){
        Huge c;
        c.init("0");
        for (int i=0;i<len;i++)
            for (int j=0;j<v.len;j++){
                c.Num[i+j]+=Num[i]*v.Num[j];
                if (c.Num[i+j]>=BASE){
                    c.Num[i+j+1]+=c.Num[i+j]/BASE;
                    c.Num[i+j]%=BASE;
                }
            }
        c.len=len+v.len;
        while (c.Num[c.len]==0 && c.len>=0) c.len--;
        len=c.len+1;
        for (int i=0;i<len;i++) Num[i]=c.Num[i];
        //return (*this);
    }
    bool operator<(const Huge &v){
        if (len!=v.len) return len<v.len;
        for (int i=len-1;i>=0;i--)
            if (Num[i]!=v.Num[i]) return Num[i]<v.Num[i];
        return 0;
    }
};
int low[MAXN],dfn[MAXN],tarjan_bcc[MAXN];
bool vis[MAXN],pis[NM];
int Num[NM];
vector<int>vec[NM];
int st[NM],tot,cnt,num;
typedef struct node{
    int x,y;
}node;
node d[NM];
Huge ans,ans1;
string trans(int x){
    string y;
    while(x){
    int t1=x%10;x-=t1;x/=10;
    y.push_back((char)(t1+'0'));
    }
    reverse(y.begin(),y.end());
    return y;
}
void tarjan_Bcc(int x,int pre){
    vis[x]=1;low[x]=dfn[x]=++cnt;
    link(x){
    if(vis[j->t]&&dfn[j->t]<dfn[x]&&j->t!=pre){
        st[++tot]=j->v;pis[j->v]=1;
        low[x]=min(low[x],dfn[j->t]);
    }
    else if(!vis[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++;vec[num].clear();
        while(1){
            int y=st[tot--];
            if(pis[y])Num[num]++;
            if(tarjan_bcc[d[y].x]!=num){
            vec[num].pb(d[y].x);
            tarjan_bcc[d[y].x]=num;
            }
            if(tarjan_bcc[d[y].y]!=num){
            vec[num].pb(d[y].y);
            tarjan_bcc[d[y].y]=num;
            }
            if(j->v==y)break;
        }
        if(Num[num]==1)ans1.init(trans(vec[num].size()+1)),ans*=ans1;
        }
    }
    }
}
int n,m;
int main(){
    int cnt1=0;
    n=read();m=read();
    ans.init(trans(1));
    inc(i,1,m){
    int k=read();int last=read();
    inc(j,2,k){
        int x=read();cnt1++;
        d[cnt1].x=x;d[cnt1].y=last;
        add(x,last,cnt1);
        add(last,x,cnt1);
        last=x;
    }
    }
    int cnt2=0;
    inc(i,1,n)if(!vis[i])tarjan_Bcc(i,0),cnt2++;
    if(cnt2>1){printf("0\n");return 0;}
    /*cout<<num<<" "<<cnt<<endl;
    inc(i,1,num){
    for(int j=0;j<vec[i].size();j++)cout<<vec[i][j]<<" ";
    cout<<endl;
    }*/
    inc(i,1,num)if(Num[i]>1){printf("0\n");return 0;}
    cout<<ans<<'\n';
    return 0;
}

BZOJ 2125 最短路

题目链接: BZOJ2125

题意:

给一个仙人掌图,$q$次查询两点之间的最短路径

题解:

对仙人掌图构造圆方树,对于查询的两个点,若其$LCA$为圆点,则直接输出圆方树上的路径和即可,若其$LCA$为方点,则两个倍增到其方点表示的点双环上,再决定走哪侧更优即可.

注意构造圆方树时 如果一条边是圆圆边，那么就是原来的边权，如果是圆方边，那么边权等于环的根到那个圆点的最短路径长度.

代码实现:

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
#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,ll>
#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=8e5+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,q;
typedef struct node{
    int x,y,z;
}node;
node d[MAXN];
int dfn[MAXN],low[MAXN];
int st[MAXN],tot;
bool vis[MAXN];
vector<pii>vec[MAXN];
int cnt,num;
ll sum[MAXN],Sum[MAXN];
vector<int>p[MAXN];
void trajan_Bcc(int x,int pre){
    vis[x]=1;dfn[x]=low[x]=++cnt;
    link(x){
	if(vis[j->t]&&dfn[x]>dfn[j->t]&&j->t!=pre){
	    st[++tot]=j->v;
	    low[x]=min(low[x],dfn[j->t]);
	}
	else if(!vis[j->t]){
	    st[++tot]=j->v;sum[j->t]=sum[x]+d[j->v].z;
	    trajan_Bcc(j->t,x);
	    low[x]=min(low[x],low[j->t]);
	    if(low[j->t]>=dfn[x]){
		if(st[tot]!=j->v){
		    num++;int y=st[tot--];
		    Sum[num-n]+=d[y].z;
		    if(dfn[d[y].x]>dfn[d[y].y])p[num-n].pb(d[y].x);
		    else p[num-n].pb(d[y].y);
		    while(1){
			y=st[tot--];Sum[num-n]+=d[y].z;
			if(dfn[d[y].x]<dfn[d[y].y])p[num-n].pb(d[y].x);
			else p[num-n].pb(d[y].y);
			if(y==j->v)break;
		    }
		    reverse(p[num-n].begin(),p[num-n].end());
		    for(int i=1;i<p[num-n].size();i++){
			ll t1=sum[p[num-n][i]]-sum[x];
			vec[num].pb(mp(p[num-n][i],min(t1,Sum[num-n]-t1)));
		    }
		    vec[x].pb(mp(num,0));
		}
		else{
		    int y=st[tot];tot--;
		    vec[x].pb(mp(j->t,d[y].z));
		}
	    }
	}
    }
}
int fa[MAXN][21],dep[MAXN],son[MAXN],Num[MAXN];
ll sum1[MAXN];
void dfs(int x,int pre,int deep){
    fa[x][0]=pre;dep[x]=deep+1;Num[x]=1;
    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=0;i<vec[x].size();i++){
	if(vec[x][i].first==pre)continue;
	sum1[vec[x][i].first]=sum1[x]+vec[x][i].second;
	dfs(vec[x][i].first,x,deep+1);
	Num[x]+=Num[vec[x][i].first];
	if(son[x]==-1||Num[vec[x][i].first]>Num[son[x]])son[x]=vec[x][i].first;
    }
}
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].first!=fa[x][0]&&vec[x][i].first!=son[x])_dfs(vec[x][i].first,vec[x][i].first);
}
int Tp(int x,int y){
    int tmp=dep[x]-dep[y];
    for(int i=20;i>=0;i--){
	if(dep[fa[x][i]]>dep[y])x=fa[x][i];
    }
    return x;
}
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][0];xx=tp[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
int Pos(int x,int y){
    int l=1;int r=p[y].size();int ans;
    while(l<=r){
	int mid=(l+r)>>1;
	if(dfn[p[y][mid-1]]>=dfn[x])ans=mid,r=mid-1;
	else l=mid+1;
    }
    return ans;
}
int main(){
    n=read();m=read();q=read();
    inc(i,1,m)d[i].x=read(),d[i].y=read(),d[i].z=read(),add(d[i].x,d[i].y,i),add(d[i].y,d[i].x,i);
    num=n;
    trajan_Bcc(1,0);
    inc(i,1,num)son[i]=-1;
    dfs(1,0,0);
    _dfs(1,1);
    int x,y;
    while(q--){
	x=read();y=read();
	int lca=Lca(x,y);
	if(lca<=n)printf("%lld\n",sum1[x]+sum1[y]-2*sum1[lca]);
	else{
	    int xx=Tp(x,lca);int yy=Tp(y,lca);
	    ll ans=sum1[x]-sum1[xx]+sum1[y]-sum1[yy];
	    int t1=Pos(xx,lca-n);int t2=Pos(yy,lca-n);
	    if(t1>t2)swap(t1,t2);
	    ll ans1=sum[p[lca-n][t2-1]]-sum[p[lca-n][t1-1]];
	    ans+=min(Sum[lca-n]-ans1,ans1);
	    printf("%lld\n",ans);
	}
    }
    return 0;
}

BZOJ 1023 [SHOI2008]cactus仙人掌图

题目链接:BZOJ1023

题意:

求仙人掌图的直径

题解:

对仙人掌图构造圆方树,对于普通的树形结构求树的直径,我们考虑维护链的最大和次大值,做个树形DP即可,对于圆方树,我们对圆点和方点分开考虑,圆点仍然按照普通的树形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
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
164
165
166
167
168
169
170
#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 int NM=1e6+10;
const double eps=1e-8;
const int inf=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 dfn[MAXN],low[MAXN],n,m,sum[MAXN];
vector<int>p[MAXN];
vector<pii>vec[MAXN];
int st[MAXN],tot,cnt,num;
int Sum[MAXN];
typedef struct node{
    int x,y;
}node;
node que[NM];
void init(){
    inc(i,1,n)sum[i]=0;
    for(int i=1;i<=num;i++)vec[i].clear(),dfn[i]=low[i]=0;
    for(int i=1;i<=num-n;i++)p[i].clear(),Sum[i]=0;
}
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){
	    low[x]=min(low[x],dfn[j->t]);
	    st[++tot]=j->v;
	}
	else if(!dfn[j->t]){
	    st[++tot]=j->v;sum[j->t]=sum[x]+1;
	    tarjan_Bcc(j->t,x);
	    low[x]=min(low[x],low[j->t]);
	    if(low[j->t]>=dfn[x]){
		if(st[tot]==j->v)vec[x].pb(mp(j->t,1)),tot--;
		else{
		    num++;p[num-n].clear();
		    int y=st[tot--];
		    if(dfn[que[y].x]>dfn[que[y].y])p[num-n].pb(que[y].x);
		    else p[num-n].pb(que[y].y);
		    while(1){
			y=st[tot--];
			if(dfn[que[y].x]>dfn[que[y].y])p[num-n].pb(que[y].y);
			else p[num-n].pb(que[y].x);
			if(y==j->v)break;
		    }
		    reverse(p[num-n].begin(),p[num-n].end());
		    Sum[num-n]=p[num-n].size();
		    for(int i=1;i<p[num-n].size();i++){
			int c=sum[p[num-n][i]]-sum[x];
			vec[num].pb(mp(p[num-n][i],min(c,Sum[num-n]-c)));
		    }
		    vec[x].pb(mp(num,0));
		}
	    }
	}
    }
}
int maxx[MAXN],ans[MAXN];
int rt,cntk;
typedef struct Node{
    int l,r,maxx,maxx1;
}Node;
Node d[MAXN*21];
int k1,k2;
void update(int &x,int l,int r,int t){
    if(!x)x=++cntk,d[x].l=d[x].r=0,d[x].maxx=d[x].maxx1=-inf;
    if(l==r){d[x].maxx=k1-k2;d[x].maxx1=k1+k2;return ;}
    int mid=(l+r)>>1;
    if(t<=mid)update(d[x].l,l,mid,t);
    else update(d[x].r,mid+1,r,t);
    d[x].maxx=d[x].maxx1=-inf;
    if(d[x].l)d[x].maxx=max(d[x].maxx,d[d[x].l].maxx),d[x].maxx1=max(d[x].maxx1,d[d[x].l].maxx1);
    if(d[x].r)d[x].maxx=max(d[x].maxx,d[d[x].r].maxx),d[x].maxx1=max(d[x].maxx1,d[d[x].r].maxx1);
}
int ans1;
void query1(int x,int l,int r,int ql,int qr){
    if(!x)return ;
    if(ql<=l&&r<=qr){ans1=max(ans1,d[x].maxx);return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query1(d[x].l,l,mid,ql,qr);
    if(qr>mid)query1(d[x].r,mid+1,r,ql,qr);
}
void query2(int x,int l,int r,int ql,int qr){
    if(!x)return ;
    if(ql<=l&&r<=qr){ans1=max(ans1,d[x].maxx1);return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query2(d[x].l,l,mid,ql,qr);
    if(qr>mid)query2(d[x].r,mid+1,r,ql,qr);
}
void dfs(int x,int pre){
    for(int i=0;i<vec[x].size();i++){
	if(vec[x][i].first==pre)continue;
	dfs(vec[x][i].first,x);
	maxx[x]=max(maxx[x],maxx[vec[x][i].first]+vec[x][i].second);
	ans[x]=max(ans[x],ans[vec[x][i].first]);
    }
    if(x<=n){
	int maxx1=0,maxx2=0;
	for(int i=0;i<vec[x].size();i++){
	    if(vec[x][i].first==pre)continue;
	    int y=maxx[vec[x][i].first]+vec[x][i].second;
	    if(y>maxx1)maxx2=maxx1,maxx1=y;
	    else if(y>maxx2)maxx2=y;
	}
	ans[x]=max(ans[x],maxx1+maxx2);
    }
    else{
	rt=0;cntk=0;int sz=p[x-n].size();
	for(int i=0;i<p[x-n].size();i++){
	    k1=maxx[p[x-n][i]];k2=i;
	    update(rt,1,2*sz,i+1);
	    k1=maxx[p[x-n][i]];k2=i+sz;
	    update(rt,1,2*sz,1+i+sz);
	}
	for(int i=0;i<p[x-n].size();i++){
	    int y=sz+i+1;int t=sz/2;
	    ans1=-inf;query1(rt,1,2*sz,y-t,y-1);
	    ans[x]=max(ans[x],maxx[p[x-n][i]]+ans1+y-1);
	    ans1=-inf;query1(rt,1,2*sz,y-sz+1,y-t-1);
	    ans[x]=max(ans[x],maxx[p[x-n][i]]-y+1+ans1+sz);
	}
    }
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
    memset(h,0,sizeof(h));o=e;
    int cnt1=0;
    int x,y,k;
    num=n;
    inc(i,1,m){
	k=read();x=read();
	inc(j,2,k){
	    y=read();
	    cnt1++;que[cnt1].x=x;que[cnt1].y=y;
	    add(x,y,cnt1);add(y,x,cnt1);
	    x=y;
	}
    }
    tarjan_Bcc(1,0);
    inc(i,1,num)maxx[i]=ans[i]=0;
    dfs(1,0);
    printf("%d\n",ans[1]);
    init();
    }
    return 0;
}

BZOJ 4316 小C的独立集

题目链接: BZOJ4316

题意:

求仙人掌图中的最大独立集(在无向图中选出若干个点，这些点互相没有边连接，并使取出的点尽量多)

题解:

将仙人掌图转化成圆方树,对于每个点做一个0/1DP,还是对于园方点分情况讨论,对于圆点做普通树形DP即可,对于方点,其$dp[0]$表示其父亲节点不被选取时点的最多个数,$dp[1]$表示其父亲节点被选取时点的最多个数,分类讨论转移下即可

代码实现:

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
#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];
int dfn[MAXN],low[MAXN];
vector<int>vec[MAXN],p[MAXN];
int st[MAXN],tot,cnt,num;
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){
	    low[x]=min(low[x],dfn[j->t]);
	    st[++tot]=j->v;
	}
	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]){
		if(st[tot]==j->v)vec[j->t].pb(x),vec[x].pb(j->t),tot--;
		else{
		    num++;int y=st[tot--];
		    if(dfn[que[y].x]>dfn[que[y].y])p[num-n].pb(que[y].x);
		    else p[num-n].pb(que[y].y);
		    while(1){
			y=st[tot--];
			if(dfn[que[y].x]<dfn[que[y].y])p[num-n].pb(que[y].x);
			else p[num-n].pb(que[y].y);
			if(j->v==y)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);
		    }
		}
	    }
	}
    }
}
int dp[MAXN][2],dp1[MAXN][2];
void dfs(int x,int pre){
    for(int i=0;i<vec[x].size();i++){
	if(vec[x][i]==pre)continue;
	dfs(vec[x][i],x);
    }
    if(x<=n){
	int maxx1=0,maxx2=0;
	for(int i=0;i<vec[x].size();i++){
	    if(vec[x][i]==pre)continue;
	    int y=vec[x][i];
	    if(y<=n)maxx1+=max(dp[y][0],dp[y][1]),maxx2+=dp[y][0];
	    else maxx1+=dp[y][0],maxx2+=dp[y][1];
	}
	dp[x][0]=maxx1;dp[x][1]=maxx2+1;
    }
    else{
	int sz=p[x-n].size();
	for(int i=0;i<sz;i++)p[x-n].pb(p[x-n][i]);
	for(int i=0;i<p[x-n].size();i++){
	    if(p[x-n][i]!=pre)continue;
	    for(int j=i+1;j<i+sz;j++){
		dp1[p[x-n][j]][0]=dp[p[x-n][j]][0]+max(dp1[p[x-n][j-1]][0],dp1[p[x-n][j-1]][1]);
		dp1[p[x-n][j]][1]=dp[p[x-n][j]][1]+dp1[p[x-n][j-1]][0];
	    }
	    dp[x][0]=max(dp1[p[x-n][i+sz-1]][0],dp1[p[x-n][i+sz-1]][1]);
	    dp[p[x-n][i+1]][1]=0;
	    for(int j=i+1;j<i+sz;j++){
		dp[p[x-n][j]][0]=dp[p[x-n][j]][0]+max(dp[p[x-n][j-1]][0],dp[p[x-n][j-1]][1]);
		dp[p[x-n][j]][1]=dp[p[x-n][j]][1]+dp[p[x-n][j-1]][0];
	    }
	    dp[x][1]=dp[p[x-n][i+sz-1]][0];
	    break;
	}
    }
}
int main(){
    n=read();m=read();
    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);
    }
    num=n;
    tarjan_Bcc(1,0);
    dfs(1,0);
    printf("%d\n",max(dp[1][0],dp[1][1]));
    return 0;
}

CODEFORCES 487E Tourists

题目链接: cf487E

题意:

给一个连通的无向图,有点权.要求支持两种操作: 查询x,y简单路径上的最小点权;修改x的点权为w;

题解:

一般而言缩环的姿势有三种:点双,边双,联通分量 这个题我们考虑点双缩环,至于为什么,读者可以从点双的性质出发即可.我们类似圆方树,对于每个点双分量用一个方点代替,其他点以菊花图的形式链接方点,因为可能存在一些点存在多个点双分量,这样修改时复杂度就会退化,那么我们这个方点仅代表其儿子节点的最小值,再查询时,若$LCA$是方点,还需要与其$LCA$的父亲进行比较,修改的话,用$multiset$来维护每个方点对应的最小值.然后问题就成了,在树上查询一条链的最小点权.树链剖分+线段树模板题

代码实现:

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
#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=5e5+10;
const double eps=1e-8;
const int inf=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,q;
int a[MAXN];
typedef struct node{
    int x,y;
}node;
node que[MAXN];
int dfn[MAXN],low[MAXN];
vector<int>vec[MAXN],p[MAXN];
int num,tot,cnt,st[MAXN],bcc_pos[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){
	    low[x]=min(low[x],dfn[j->t]);
	    st[++tot]=j->v;
	}
	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[que[y].x]!=num)p[num-n].pb(que[y].x),bcc_pos[que[y].x]=num;
		    if(bcc_pos[que[y].y]!=num)p[num-n].pb(que[y].y),bcc_pos[que[y].y]=num;
		    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);
		}
	    }
	}
    }
}
multiset<int>s[MAXN];
int fa[MAXN],son[MAXN],Num[MAXN],dep[MAXN];
void dfs(int x,int pre,int deep){
    fa[x]=pre;Num[x]=1;dep[x]=deep+1;
    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(x>n)s[x-n].insert(a[vec[x][i]]);
	if(son[x]==-1||Num[son[x]]<Num[vec[x][i]])son[x]=vec[x][i];
    }
    if(x>n)a[x]=(*s[x-n].begin());
}
int pos[MAXN],Fpos[MAXN],tp[MAXN];
int cnt1;
void _dfs(int x,int td){
    pos[x]=++cnt1;Fpos[pos[x]]=x;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 minn[MAXN<<2];
void built(int x,int l,int r){
    if(l==r){minn[x]=a[Fpos[l]];return ;}
    int mid=(l+r)>>1;
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
    minn[x]=min(minn[x<<1],minn[x<<1|1]);
}
void update(int x,int l,int r,int t,int k){
    if(l==r){minn[x]=k;return ;}
    int mid=(l+r)>>1;
    if(t<=mid)update(x<<1,l,mid,t,k);
    else update(x<<1|1,mid+1,r,t,k);
    minn[x]=min(minn[x<<1],minn[x<<1|1]);
}
int ans;
void query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){ans=min(ans,minn[x]);return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query(x<<1,l,mid,ql,qr);
    if(qr>mid)query(x<<1|1,mid+1,r,ql,qr);
}
void solve(int x,int y){
    int xx=tp[x];int yy=tp[y];
    ans=inf;
    while(xx!=yy){
	if(dep[xx]<dep[yy])swap(xx,yy),swap(x,y);
	query(1,1,num,pos[xx],pos[x]);
	x=fa[xx];xx=tp[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    query(1,1,num,pos[x],pos[y]);
    if(x>n){
	ans=min(ans,a[fa[x]]);
    }
    printf("%d\n",ans);
}
char str[11];
int main(){
    n=read();m=read();q=read();
    inc(i,1,n)a[i]=read();
    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);
    }
    num=n;
    tarjan_Bcc(1,0);
    inc(i,1,num)son[i]=-1;
    dfs(1,0,0);_dfs(1,0);
    built(1,1,num);
    int x,y;
    while(q--){
	scanf("%s",str);
	if(str[0]=='C'){
	    x=read();y=read();
	    if(fa[x]>n){
		s[fa[x]-n].erase(s[fa[x]-n].lower_bound(a[x]));
		s[fa[x]-n].insert(y);
		a[fa[x]]=(*s[fa[x]-n].begin());
		update(1,1,num,pos[fa[x]],a[fa[x]]);
		a[x]=y;
		update(1,1,num,pos[x],a[x]);
	    }
	    else a[x]=y,update(1,1,num,pos[x],a[x]);
	}
	else{
	    x=read();y=read();
	    solve(x,y);
	}
    }
    return 0;
}