Luogu CF555E 【Case of Computer Network】

2021-03-13 11:37

阅读：462

标签：不同惊奇 put ++ ext 差分 get net 问题

其实如果这是一颗树的话很好搞，把\(s\)到\(lca(s,t)\) 向上连，\(lca(s,t)\)到\(t\)向下连即可(然而事情并不是这样子的...)。
我们考虑什么样的情况是一定可行的呢？每两个点之间都有两条以上的路径，那就可以一边向前，一边向后，绝对可以。也就是求双联通分量以内是一定可以的，所以考虑缩点。惊奇的发现得到了一片森林（两点之间最多一条边，否则就被缩点了），那不就好搞了嘛！特判在不同树上的情况，直接在缩点的时候暴力搞定就行。在同一棵树上可以树剖/树上差分维护。最后一遍dfs判定标记是否重复就行了
那么现在问题就是怎没求双联通分量了...我并不会诶....（~~现场学习~~）

#include 

#define R register
const int MAXN=2e5+10;
const int MAXM=MAXN‘9‘||a=‘0‘&&asiz[son[x]]) son[x]=y;
	}
}

inline void dfs2(int x,int topx)
{
	top[x]=topx;
	if(son[x]) dfs2(son[x],topx);
	for(R int i=head2[x];i;i=e2[i].next)
	{
		int y=e2[i].to;
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}

inline int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]>dep[top[y]])
			x=fa[top[x]];
		else
			y=fa[top[y]];
	}
	return dep[x]

Luogu CF555E 【Case of Computer Network】

标签：不同惊奇 put ++ ext 差分 get net 问题

原文地址：https://www.cnblogs.com/HN-wrp/p/12819924.html

上一篇：原生JS简单封装JSONP跨域获取数据

下一篇：JS实现倒计时

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Luogu CF555E 【Case of Computer Network】
文章链接：http://soscw.com/essay/64103.html

亲，登录后才可以留言！

Luogu CF555E 【Case of Computer Network】

评论

热门文章

推荐文章

最新文章

置顶文章