首页 > 其他分享 >基环树和笛卡尔树

基环树和笛卡尔树

时间:2024-06-23 14:58:33浏览次数:15  
标签:笛卡尔 int top 基环树 fa root dp

基环树

就是比平常的树多一条边,有 \(n\) 条边,也就有一个环在里面。

基本思想就是断环,跑树形 \(dp\),或者用拓扑排序判环去跑环形 \(dp\)。

树的直径

今天才了解到的,用两遍 \(dfs\) 跑。

首先第一遍找到离根节点最远的节点 \(u_1\),

然后再从 \(u_1\) 找到离它最远的节点 \(u_2\),那么树链 \((u_1,u_2)\) 就是树的直径。

在后面很有用。

#3437. [ZJOI2008]骑士

类似于树形 dp 的思路(没有上司的舞会)。

考虑状态转移方程:

\[dp[u][1]=\sum dp[v][0]+a[u] \]

\[dp[u][0]=\sum \max(dp[v][0],dp[v][1]) \]

其中 \(v\) 表示 \(u\) 的子节点。

然后基环树的思路是先找环,找到环的根之后跑树形 dp。

void dfs(int u)
{
	vis[u]=1;
	dp[u][0]=0,dp[u][1]=a[u];
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=root)
		{
			dfs(v);
			dp[u][0]+=max(dp[v][0],dp[v][1]);
			dp[u][1]+=dp[v][0];
		}
		else dp[v][1]=-1145141919;
	}
}
void find(int x)
{
	vis[x]=1;
	root=x;
	while(!vis[fa[root]])
	{
		root=fa[root];
		vis[root]=1;
	}
	dfs(root);
	int tmp=max(dp[root][0],dp[root][1]);
	vis[root]=1;
	root=fa[root];
	dfs(root);
	ans+=max(tmp,max(dp[root][1],dp[root][0]));
}

#P1203. 「NOIP2018」旅行

P3533 [POI2012] RAN-Rendezvous

妈呀,打了一下午成小孩了。

调了一万次甚至动用科技,最后发现树剖炸了、

题目给出一个基环内向树森林,我们首先预处理出每个点所属环上的根节点 \(cir\) 是谁,再对分别对每棵树进行树剖。

然后通过 \(dfs\) 计算每个环的编号 \(id\) 和长度 \(len\)。

考虑两个点的状态进行分类讨论:

  • 两点位于不同的基环树中

通过找环的时候给每个环进行编号,查询两点在环上根节点所属环是否一样进行判断;

  • 两点位于同一基环树的同一子树中

意思是两点的 \(cir\) 相同,我们可以直接查询 \(lca(a,b)\) 作为答案;

  • 两点位于同一基环树不同子树中

比较两个 \(cir\) 作为相遇点,哪个更符合要求即可。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	register int s=0,w=1;
	register char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
	{
		s=(s<<1)+(s<<3)+(c^48);c=getchar();
	}return s;
}
int n,m;
const int N=5e5+1;
vector<int>e[N],uu[N];
int indeg[N];
int q[N*2],tt;
int cir[N];
struct HPD{
	int siz[N],dep[N],son[N],fa[N];
	int id[N],tim=0,top[N];
	void dfs1(int u,int fat)
	{
		siz[u]=1,fa[u]=fat;
		if(!indeg[u]) dep[u]=dep[fat]+1;
		cir[u]=cir[fat];
		for(int v:uu[u])
		{
			if(v==fat||indeg[v]) continue;
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]]) son[u]=v;
		}
	}
	void dfs2(int u,int t)
	{
		top[u]=t;
		if(son[u]) dfs2(son[u],t);
		for(int v:uu[u])
		{
			if(v==fa[u]||indeg[v]||v==son[u]) continue;
			dfs2(v,v);
		}
	}
	int lca(int u,int v)
	{
		while(top[u]!=top[v])
		{
			if(dep[top[u]]>=dep[top[v]]) u=fa[top[u]];
			else v=fa[top[v]];
		}
		return dep[u]<dep[v]?u:v;
	}
}hpd;
bool vis[N];
int len[N],pos[N];
int id[N],cur;
void dfs(int u,int le)
{
	len[u]=le,vis[u]=1,pos[u]=le;
	for(int v:e[u])
	{
		if(vis[v]||!indeg[v]) continue;
		id[v]=id[u];
		dfs(v,le+1);
		len[u]=len[v];
	}
}
inline bool cmp(int x1,int y,int x2,int y2)
{
	if(max(x1,y)!=max(x2,y2)) return max(x1,y)<max(x2,y2);
	if(min(x1,y)!=min(x2,y2)) return min(x1,y)<min(x2,y2);
	return x1>=y;
}
int main()
{
	n=read(),m=read();
	register int v;
	for(int i=1;i<=n;i++)
	{
		v=read();
		e[i].push_back(v);
		indeg[v]++;
		uu[v].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		if(!indeg[i]) q[++tt]=i;
	}
	register int now;
	while(tt!=0)
	{
		now=q[tt];tt--;
		v=e[now][0];
		indeg[v]--;
		if(!indeg[v]) q[++tt]=v;
	}
	for(int i=1;i<=n;i++)
	{
		if(indeg[i])
		{
			cir[i]=i;
			hpd.dfs1(i,i);
			hpd.dfs2(i,i);
			if(!vis[i]) id[i]=++cur,dfs(i,1);
		} 
	}
	register int a,b;
	while(m--)
	{
		a=read(),b=read();
		if(id[cir[a]]!=id[cir[b]])
		{
			printf("-1 -1\n");continue;
		}
	//	cout<<cir[a]<<" "<<cir[b]<<endl;
		if(cir[a]==cir[b])
		{
			int lc=hpd.lca(a,b);
		//	cout<<lc<<endl;
			printf("%d %d\n",hpd.dep[a]-hpd.dep[lc],hpd.dep[b]-hpd.dep[lc]);
		}
		else
		{
			int cira=pos[cir[a]],cirb=pos[cir[b]];
			int mod=len[cir[a]];
		//	cout<<cira<<" "<<cirb<<endl;
			int t1=hpd.dep[a]+(cirb-cira+mod)%mod;
			int t2=hpd.dep[b]+(cira-cirb+mod)%mod;
			if(cmp(hpd.dep[a],t2,t1,hpd.dep[b])) printf("%d %d\n",hpd.dep[a],t2);
			else printf("%d %d\n",t1,hpd.dep[b]);
		}
	}
}

标签:笛卡尔,int,top,基环树,fa,root,dp
From: https://www.cnblogs.com/ccjjxx/p/18250956

相关文章

  • 基环树和笛卡尔树
    1.基环树定义:有\(n\)个点和\(n\)条边的图,就是给树连了一条边,此时图中恰好只有一个环解决这类问题时,通常断环,变成普通的树的问题,然后再特殊处理环P2607[ZJOI2008]骑士click断环成树后就跟没上司一样是个树形dp,注意森林,longlong就行了,具体细节见这里P5022[NOIP2018提高组......
  • 过滤条件之分组 group by、having、distinct、order by、limit、正则、多表查询和子查
    【一】过滤条件之分组groupby【1】引入--按照指定条件对所有数据进行分组--对员工进行分组按照年龄/部门--...select*from*where*groupby*;【2】按照部门分组(1)查询数据select*fromempgroupbypost;#第一次使用部门分组会报错mysql>select*f......
  • 基环树
    基环树1.定义基环树是一个由n个点及n条边组成的连通图,其比树多出一条边,所以称作基环树。2.分类基环树分为无向基环树和有向基环树。而有向基环树又分为内向基环树和外向基环树。内向基环树,即每个点出度为1的基环树;外向基环树,即每个点入度为1的基环树。3.解决方式对于有关......
  • 笛卡尔树
    笛卡尔树引入笛卡尔树是一种二叉树,每一个节点由一个键值二元组\((k,w)\)构成。要求k满足二叉搜索树的性质,而w满足堆的性质。一个有趣的事实是,如果笛卡尔树的\(k,w\)键值确定,且k互不相同,w互不相同,那么这个笛卡尔树的结构是唯一的。上面这棵笛卡尔树相当于把数组元素当作键值w,......
  • 基环树
    基环树的定义为:一个有向或无向图中,只含有一个环的图,形式化的表达为:关于这种形状关键点主要在于找环,那么我们可以一步一步的去寻找,当这个点走着走着走到了某个环里,我们可以直接遍历整个环,然后打个标记,这样环就找到了具体的例题:E-ReachabilityinFunctionalGraph本题就是一......
  • 基环树找环
    abc167_dTeleporter#include<bits/stdc++.h>#defineptprintf(">>>")#definemid(((l)+(r))/2)usingnamespacestd;typedeflonglongll;typedeflongdoubleld;constllN=1e6+10,inf=1e18+10,mod=1e9+7;vector<ll>G[N];map&......
  • 赛克oj The diameter of a rectangle(笛卡尔树)
    赛氪OJ-专注于算法竞赛的在线评测系统(saikr.com)这题是hduoj1506的加强版,区别在于宽度不是固定为1了,思路差不多,也是使用笛卡尔树。参考hduoj1506(笛卡尔树)-Venux-博客园(cnblogs.com)1#defineIOstd::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)2#definebu......
  • hduoj 1506(笛卡尔树)
    Problem-1506(hdu.edu.cn)题意坐标轴给定一些矩形,紧密排在一起,每个矩形宽度固定为1,问形成的图案中最大可以组成的矩形面积。思路常规思路是可以用单调栈分别找两边的合法边界,这里使用笛卡尔树。笛卡尔树实现了堆的性质,并且对原数组建立的笛卡尔树进行中序遍历为原数组的顺......
  • [NOI2009] 二叉查找树 & 笛卡尔树学习笔记
    这个题:二叉搜索树原理认识+区间dp;只要熟练相关算法就一定可以做出来。但我不行。。。我们学习一下笛卡尔树:什么垃圾东西,不学了。发现这个题是l蓝书上一道题jqb。二叉查找树又有一个性质:二叉查找树的中序遍历是其代表的序列从小到大排序的结果。而无论Treap如何旋转,其都......
  • 笛卡尔树学习笔记
    笛卡尔树引入是一种二叉树,每个节点由一个二元组\((k,w)\)形成。\(k\)满足二叉搜索树的性质,\(w\)满足堆的性质。上面这棵笛卡尔树相当于把数组元素值当作键值\(w\),而把数组下标当作键值\(k\)。显然可以发现,这棵树的键值\(k\)满足二叉搜索树的性质,而键值\(w\)满足小根......