首页 > 其他分享 >CF231E Cactus

CF231E Cactus

时间:2023-08-28 09:44:04浏览次数:45  
标签:int st fa CF231E dfn low Cactus 300001

CF231E Cactus

点仙人掌的性质:每个点最多只在一个环里。

image.png

对于 \(u,v\) 之间的路径,显然一定是由一些链和一些环拼接而成的。

对于链,只能按照唯一的方式行走。

对于环,有两种走的方案:顺时针和逆时针走。

各个环间互不影响,乘法原理得到答案就是 \(2\) 的环个数次方。

边双所点后维护前缀和,变成树上 LCA 问题,倍增或树剖或 tarjan 即可。

inline int power(int x,int y)
{
	int ans=1;
	for(;y;x=x*x%MOD,y>>=1)if(y&1)ans=ans*x%MOD;
	return ans;
}
int n,m,q,tot,cnt,num,col[300001],val[300001],dep[300001],fa[300001][21],x[300001],y[300001],dfn[300001],low[300001],cut[200001],head[300001],to[500001],nex[500001];
vector<int> T[300001];
stack<int> st;
inline void add(int x,int y){to[++cnt]=y,nex[cnt]=head[x],head[x]=cnt;}
void tarjan(int k,int from)
{
	dfn[k]=low[k]=++tot,st.push(k);
	for(int i=head[k];i;i=nex[i])
	{
		if(i==(from^1))continue;
		if(!dfn[to[i]])
		{
			tarjan(to[i],i),low[k]=min(low[k],low[to[i]]);
			if(low[to[i]]>dfn[k])cut[i]=cut[i^1]=1;
		}
		else low[k]=min(low[k],dfn[to[i]]);
	}
	if(dfn[k]==low[k])
	{
		col[k]=++num;int y=1;
		while(st.top()!=k)++y,col[st.top()]=num,st.pop();
		st.pop();
		if(y>1)val[num]=1;
	}
}
void dfs(int k,int father)
{
	val[k]+=val[father],dep[k]=dep[father]+1,fa[k][0]=father;
	for(int i=1;i<=20;++i)fa[k][i]=fa[fa[k][i-1]][i-1];
	for(auto to:T[k])if(to!=father)dfs(to,k);
}
inline int LCA(int x,int y)
{
	if(dep[x]>dep[y])swap(x,y);
	for(int i=20;i>=0;--i)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];
	for(int i=20;i>=0;--i)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return x==y?x:fa[x][0];
}
inline void mian()
{
	cnt=1,read(n,m);int a,b,lca;
	for(int i=1;i<=m;++i)read(x[i],y[i]),add(x[i],y[i]),add(y[i],x[i]);
	for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i,0);
	for(int i=1;i<=m;++i)if(col[x[i]]!=col[y[i]])T[col[x[i]]].eb(col[y[i]]),T[col[y[i]]].eb(col[x[i]]);
	dfs(1,0),read(m);
	while(m--)read(a,b),a=col[a],b=col[b],lca=LCA(a,b),write(power(2,val[a]+val[b]-val[lca]-val[fa[lca][0]]),'\n');
}

标签:int,st,fa,CF231E,dfn,low,Cactus,300001
From: https://www.cnblogs.com/WrongAnswer90-home/p/17661456.html

相关文章

  • CodeForces 1268E Happy Cactus
    洛谷传送门AtCoder传送门考虑一些简单的情况,比如树。设\(f_u\)为当前\(u\)能通过边权递增的路径到达的点数(包括它自己)。为了让两个点对在边权递增路径的边权最小的那条边被统计,我们倒序枚举边。当枚举到\((u,v)\)时,我们有\(f_u=f_v=f_u+f_v\)。这是因为\(u\)......
  • 300iq Contest 2 C Counting Cactus
    这个数据范围显然是要状压的。考虑一个子集\(S\),钦定他的根是\(u\)该如何转移(设为\(f(u,S)\)):\(u\)会在若干个环中,还会有若个用一条边分割的子仙人掌。也就是若干子仙人掌拼起来。自然需要再设一个\(g(u,S)\)表示\(u\)为根,且\(u\)只包含在一个环或一条边中的方案数。......
  • 「Gym102759B」Cactus Competition 题解
    传送门「Gym102759B」CactusCompetition题目大意有一个\(n\timesm\)的网格图,一个长度为\(n\)的序列\(a\),和一个长度为\(m\)的序列\(b\)。网格图中,第\(i\)......
  • E. Cactus Wall
    E.CactusWallMonocarpisplayingMinecraftandwantstobuildawallofcacti.Hewantstobuilditonafieldofsandofthesizeof$n\timesm$cells.Ini......
  • Hyperledger Cactus(一):架构初探
    Hyperledgercactus是一个区块链集成框架,能够在多个分布式账本上执行交易,最大的特点是灵活可插拔的架构,官方定义:SDKofSDKs。Cactus现在已经支持的分布式账本有Hyperledg......
  • CF856D Masha and Cactus(树上 DP+抵消贡献技巧)
    CF856DMashaandCactus我们先捞出一个根节点,那么一次旋变就是对路径上点的覆盖。设\(dp_{i,0}\)表示\(i\)没有选择时子树内最大收益,\(dp_{i,1}\)表示\(i\)选择......