lp5236 【模板】静态仙人掌(圆方树)

按照我们之前的经验,仙人掌上问题往往可以通过圆方树转化为树上问题。
我们发现,最短路在树上是一种非常容易解决的问题。只需预处理到根节点的长度然后死命跑LCA就可以了。
但是在一般图上,最短路的实时处理就会变得很困难。
我们可以尝试通过给圆方树上的边赋上特别的边权来处理这个问题。

对于圆-圆边,赋边权为原边权,这是容易理解的。
对于方点到它的父亲圆点的边,赋边权为0,对于圆点到它的父亲方点的边,赋边权为这个圆点到这个方点的父亲圆点的最短距离。

这时候我们会遇到一个问题,就是Tarjan找环的时候找不到返祖边的边权。
解决方案是记录每一个到根节点在dfs树上的距离,然后当我们找到一个环一路找爸爸并统计长度即可。

然后是计算答案,我们发现,如果询问的两个点的最近公共祖先是一个方点,那么它们的答案不能用普通方法计算。
我一开始的想法是尝试直接用某个节点到父亲方点的边权直接计算答案,但这样会导致答案错误,原因是它无法正确地区分两个点位于圆环的同一侧还是不同侧的情况。
故而,我们需要保存原来的距离它的父亲方点的靠某一侧的距离,故而当lca是方点的时候特殊判断计算即可。

 #include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

typedef long long ll;

inline ll Min(ll A,ll B){
    return A<B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline ll Abs(ll A){
	return A>0?A:-A;
}
inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}

struct ee{
    int v;
    ll w;
    int nxt;
}e[200005];
int h0[10005],h[20005],et=0;
inline void Eadd(int *H,int U,int V,ll W){
    e[++et]=(ee){V,W,H[U]};
    H[U]=et;
}
inline void add(int *H,int U,int V,ll W){
    Eadd(H,U,V,W);
    Eadd(H,V,U,W);
}
int dfn[20005],lw[20005],cnt=0,dep[20005],fa[20005][30];
ll dis[20005],sz[20005];
int nm=0;
int st[20005],tp=0;
inline void dfs0(int X){
    dfn[X]=lw[X]=++cnt;
    Fv(h0,i,X){
    	if(e[i].v==fa[X][0]){
    		continue;
		}
        if(!dfn[e[i].v]){
            fa[e[i].v][0]=X;
            dis[e[i].v]=dis[X]+e[i].w;
            dfs0(e[i].v);
            lw[X]=Min(lw[X],lw[e[i].v]);
    	}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
			if(e[i].v!=fa[X][0]&&dfn[e[i].v]<dfn[X]){
                ++nm;
                add(h,nm,e[i].v,0);
                ll len=e[i].w;
                for(int j=X;j^e[i].v;j=fa[j][0]){
                	len+=dis[j]-dis[fa[j][0]];
                }
                sz[nm]=len;
                ll nw=e[i].w;
                for(int j=X;j^e[i].v;j=fa[j][0]){
                    add(h,nm,j,Min(nw,len-nw));
                    sz[j]=nw; 
                    nw+=dis[j]-dis[fa[j][0]];
                }
            }
        }
        if(lw[e[i].v]>dfn[X]){
        	add(h,X,e[i].v,e[i].w);
		} 
    }
}

inline void dfs1(int X,int FA){
    dep[X]=dep[FA]+1;
    fa[X][0]=FA;
    Fv(h,i,X){
        if(e[i].v!=FA){
            dis[e[i].v]=dis[X]+e[i].w;
            dfs1(e[i].v,X);
        }
    }
}

int n,m,q;

inline ll calc(int X,int Y){
    int XX=X,YY=Y,lca;
    while(dep[XX]<dep[YY]){
        Swap(XX,YY);
    }
    for(int i=20;~i;--i){
        if(dep[XX]-(1<<i)>=dep[YY]){
            XX=fa[XX][i];
        }
    }
    if(XX==YY){
        lca=XX;
    }else{
        for(int i=20;~i;--i){
            if(fa[XX][i]!=fa[YY][i]){
                XX=fa[XX][i];
                YY=fa[YY][i];
            }
        }
        lca=fa[XX][0];
    }
    ll RT=dis[X]+dis[Y]-(dis[lca]<<1);
    if(lca>n){
        ll P=dis[XX]-dis[lca],Q=dis[YY]-dis[lca];
        RT-=(P+Q);
        RT+=Min(sz[lca]-Abs(sz[XX]-sz[YY]),Abs(sz[XX]-sz[YY]));
    }
    return RT;
}



void init(){
    scanf("%d%d%d",&n,&m,&q);
    nm=n;
    int u,v;
	ll w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%lld",&u,&v,&w);
        add(h0,u,v,w);
    }
    fa[1][0]=0;
    dfs0(1);
    for(int i=1;i<=nm;++i){
        dep[i]=0,dis[i]=0;
    }
    dfs1(1,0);
    for(int j=1;j<=20;++j){
        for(int i=1;i<=nm;++i){
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
    int x,y;
    for(int i=1;i<=q;++i){
        scanf("%d%d",&x,&y);
        printf("%lld\n",calc(x,y));
    }
}
int main(){
    init();
    return 0;
}

CF487E Tourists

众所周知,圆方树是用来处理图上点双相关问题的。
同时,点双又是一个和简单路径密切相关的东西。故而这一题我们可以考虑用圆方树来处理。
我们发现,如果两点之间有多条简单路径,那么它们一定处于同一个点双中。所以,我们可以把原图转化为圆方树,这样就可以用树链剖分套线段树来求解询问了。
但是题目要求要修改点权,这要怎么办呢?

一个直观的想法是暴力修改每个点周围相邻的方点。然而事实上如果出现了个菊花套菊花套菊花图的话显然是会严重TLE的。
我们考虑一种动态维护一个方点的点值的算法。我们尝试对每个方点开一个mulitiset,每当修改一个点的点权的时候就把旧的点权删去然后插入新的点权,并更新方点点值。
然而,如果每个修改的圆点周围都有很多的方点的话,这种做法仍然有TLE的风险。我们考虑对于每个圆点,只更新它的父亲方点。
它对它的儿子方点的贡献,则在询问的时候统计。
这样复杂度就对了。
这就使用了圆方树上树链剖分套线段树解决了这道题。

注意:
树链剖分中更新最大孩子的部分,这里是son!不是sz!调了我一个晚上!

#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<set>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

std::multiset<int> s[200005]; 

const int INF=2147483647;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}

struct ee{
	int v;
	int nxt;
}e[2000005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}


int dfn[200005],lw[100005];
//注意数组大小。 
int nm,cnt=0;
int st[100005],tp=0;
inline void dfs0(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
				++nm;
				for(int j=0;j!=e[i].v;--tp){
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}
int fa[200005],sz[200005],dep[200005],son[200005],top[200005],loc[200005];
inline void dfs1(int X,int FA){
	fa[X]=FA,dep[X]=dep[FA]+1,sz[X]=1;
	Fv(h,i,X){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
			sz[X]+=sz[e[i].v];
			if(sz[son[X]]<sz[e[i].v]){
				son[X]=e[i].v;
				//这里是son!不是sz!调了我一个晚上! 
			}
		}
	}
}
inline void dfs2(int X,int FA,int TP){
	dfn[X]=++cnt,loc[cnt]=X,top[X]=TP;
	if(son[X]){
		dfs2(son[X],X,TP);
	}
	Fv(h,i,X){
		if(e[i].v!=FA&&e[i].v!=son[X]){
			dfs2(e[i].v,X,e[i].v);
		}
	}
}

int n,m,q;
int a[200005];

#define MID (L+R>>1)
#define LS (X<<1)
#define RS (X<<1|1)

int tr[600005];
inline void bld(int X,int L,int R){
	if(L==R){
		tr[X]=a[loc[L]];
//		记得逆哈希 
		return;
	}
	bld(LS,L,MID);
	bld(RS,MID+1,R);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline int qry(int X,int L,int R,int A,int B){
	if(A>R||L>B){
		return INF;
	}
	if(A<=L&&R<=B){
		return tr[X];
	}
	return Min(qry(LS,L,MID,A,B),qry(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d%d%d",&n,&m,&q);
	nm=n;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	dfs0(1);
	dfs1(1,0);
	cnt=0;
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		if(fa[i]){
			s[fa[i]].insert(a[i]);
		}
	}
	for(int i=n+1;i<=nm;++i){
		a[i]=*s[i].begin();
	}
	
	bld(1,1,nm);
	char ch[3];
	int x,y;
	int ans;
	
	for(int i=1;i<=q;++i){
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0]=='C'){
			chg(1,1,nm,dfn[x],y);
			if(fa[x]){
				u=fa[x];
				s[u].erase(s[u].lower_bound(a[x]));
				s[u].insert(y);
				if(a[u]!=*s[u].begin()){
					a[u]=*s[u].begin();
					chg(1,1,nm,dfn[u],a[u]);
				}
			}
			a[x]=y;
		}else{
			ans=INF;
			while(top[x]!=top[y]){
				if(dep[top[x]]<dep[top[y]]){
					Swap(x,y);
				}
				ans=Min(ans,qry(1,1,nm,dfn[top[x]],dfn[x]));
				x=fa[top[x]];
			}
			if(dfn[x]>dfn[y]){
				Swap(x,y);
			}
			ans=Min(ans,qry(1,1,nm,dfn[x],dfn[y]));
			if(x>n){
				ans=Min(ans,a[fa[x]]);
			}
			printf("%d\n",ans);
		}
	} 
}

int main(){
	init();
	return 0;
}

lp4630 APIO2018 Duathlon 铁人两项

圆方树是一种在仙人掌图上常用的数据结构,但是这并不意味着圆方树只在仙人掌图上有用。事实上,在任何一张图上,我们都可以用相似的方法来构造一棵圆方树。
对于一张图,我们预处理出它的所有点双,然后对每一个点双建一个方点,其他处理方法和仙人掌上圆方树几乎相同。
这里的点双要如何预处理呢?我们考虑一个性质:当我们预处理出一张图的DFS树后,任何一条边属于且仅属于一个点双。
那么,我们就可以尝试找到一个点双中深度最浅的节点,然后由它构造出这个方点。
我们发现,当我们搜索完一个节点的子树后,如果子节点中的某一个节点的lw是这个节点,那么这个节点就是它所在的点双中深度最浅的节点。
这是因为,如果一个节点的lw节点是它的父节点,那么它和它的子树就没有任何返祖边能够到达比当前节点更浅的节点,也就说明如果当前节点在点双内,那么它一定是点双内最浅的节点。
有没有可能当前节点不在点双内呢?这是不可能的。如果有返祖边连向当前节点,那么当前节点显然不会成为割点;如果没有,那么当前节点所属的点双就一定只有两个点。

现在把目光投到这道题。
首先考虑点双的基本性质。我们发现,对于至少有三个点的点双,任取三个点,它们总是一对满足题意的三元组。
这是由于点双的定义,点双里没有割点,自然总是可以找到两点间的两条不相交的简单路径。
拓展这个结论,我们发现,如果一条简单路径经过一个点双,那么显然无论固定哪个点,这条路径都始终是一条简单路径。
故而,对于选定的起点和终点,我们可以分两类讨论。
倘若它们位于同一个点双,那么显然它们之间的满足题意的三元组个数恰好是这个点双的点数-2
对于不属于同一个点双的情况,它们之间有可能经过其他的点双,也有可能不经过。每经过一个点双,它们之间的满足题意的三元组个数就会加上这个点双的点的个数。
同时,答案还要加上起点和终点各自处在的点双的点数个数各自-1。
这要怎么统计呢?我们可以让每个方点的权值为点双中的点的数量,每个圆点的权值为-1,然后枚举点对统计路径和即可。
仔细一想觉得有点不对劲儿:这样的复杂度岂不是要n^2logn级别?妥妥地T啊。
正难则反,我们可以统计每个点对答案的贡献,也就是经过它的路径数乘上它本身的权值。而前者可以通过一个普通的树形DP求得。
这就做完了。

注意:
要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小,而非总节点数减去它的子树大小。故而要注意统计连通块大小。

#include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[1200005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}

int n,m;
int dfn[100005],lw[100005],cnt=0,nm=0;
int st[100005],tp=0;
int val[200005],nwsz;
long long ans=0;
inline void dfs(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	++nwsz;
//	要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小,而非总节点数减去它的子树大小。故而要注意统计连通块大小。 
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
//				注意这里应当判定的是lw(v)=dfn(u) 
				val[++nm]=1;
				for(int j=0;j!=e[i].v;--tp){
					++val[nm];
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}

int vis[200005],sz[200005];

inline void dfs2(int X){
	vis[X]=1;
	sz[X]=(X<=n);
	Fv(h,i,X){
		if(!vis[e[i].v]){
			dfs2(e[i].v);
			ans+=2ll*val[X]*sz[X]*sz[e[i].v];
			sz[X]+=sz[e[i].v];
		}
	}
	ans+=2ll*val[X]*sz[X]*(nwsz-sz[X]);
}

void init(){
	scanf("%d%d",&n,&m);
	nm=n;
	for(int i=1;i<=n;++i){
		val[i]=-1;
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			nwsz=0;
			dfs(i);
			dfs2(i);
			--tp;
		}
	}
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}

lp4244 SHOI2008 仙人掌图 II

仙人掌图是每一个点双都只有一个环的连通图。
对于一个仙人掌图,它在许多方面都有树的性质,只是其中的有一些节点被换成了环。
我们不妨依然采用一种伪树形DP的方式来处理这棵树,我们发现,非环节点的转移都是非常容易达成了,问题在于环上的节点的转移。

首先,我们要找到这个环,这可以用Tarjan算法来完成。
具体来说,我们维护两个数组:dfn和lw,其中前者表示的是某一个节点的dfs序,后者表示的是某一个节点至多走一条返祖边或者父亲边能够到达的最小dfs序。
显然,在搜索中,如果下一个节点未被访问过,我们就可以在搜索完它以后将当前节点的lw与它的lw取较小值。
否则,当前节点通向它的边一定是一条返祖边或者父亲边,那么当前节点的lw值应当与它的dfs序取较小值。

对于一个环,我们如果将它视为一个节点,我们想一想要怎么从它的「孩子」们处转移呢?
我们发现,依次枚举它的每一个孩子,答案显然是:
$$max(f_i+f_j+dis_{i,j})$$
这个式子可以使用单调队列优化。所以我们每一次把一个环提出来瞎DP一下就好了。

#include<iostream>
#include<cstdio>
#include<deque>
#define Fv(A,U) for(int A=h[U];A;A=e[A].nxt)

inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[200005];
int et=0,h[100005];
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,m;
int dfn[100005],lw[100005],dep[100005],fa[100005],cnt=0;
int ans=0,f[100005],a[100005];
std::deque<int> q;
inline void calc(int X,int Y){
	int tot=dep[Y]-dep[X]+1;
	int nw=tot;
	for(int i=Y;i!=X;i=fa[i]){
		a[nw--]=f[i];
	}
	a[nw]=f[X];
	for(int i=1;i<=tot;++i){
		a[tot+i]=a[i];
	}
	while(!q.empty()){
		q.pop_front();
	}
	q.push_back(1);
	for(int i=2;i<=(tot<<1);++i){
		while(!q.empty()&&i-q.front()>(tot>>1)){
			q.pop_front();
		}
		if(!q.empty()){
			ans=Max(ans,a[i]+a[q.front()]+i-q.front());
		}
		while(!q.empty()&&a[q.back()]-q.back()<a[i]-i){
			q.pop_back();
		}
		q.push_back(i);
	}
	for(int i=2;i<=tot;++i){
		f[X]=Max(f[X],a[i]+Min(i-1,tot-i+1));
	}
}
inline void dfs(int X,int FA){
	dfn[X]=lw[X]=++cnt;
	Fv(i,X){
		if(e[i].v!=FA){//这一句如果不加会无形降低很多点的lw值,从而使环的大小变成0。 
			if(!dfn[e[i].v]){
				fa[e[i].v]=X;
				dep[e[i].v]=dep[X]+1;
				dfs(e[i].v,X);
				lw[X]=Min(lw[X],lw[e[i].v]);
			}else{
				lw[X]=Min(lw[X],dfn[e[i].v]);
			}
			if(lw[e[i].v]>dfn[X]){
				ans=Max(ans,f[X]+f[e[i].v]+1);
				f[X]=Max(f[X],f[e[i].v]+1);
			}
		}
		
	}
	Fv(i,X){
		if(fa[e[i].v]!=X&&dfn[X]<dfn[e[i].v]){
			calc(X,e[i].v);
		}
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,x;
	for(int i=1;i<=m;++i){
		u=0;
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d",&v);
			if(u){
				add(u,v);
			}
			u=v;
		}
	}
	dfs(1,0);
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}