专栏文章

P4334 [COI 2007] Policija 题解

P4334题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipuhw0t
此快照首次捕获于
2025/12/03 18:09
3 个月前
此快照最后确认于
2025/12/03 18:09
3 个月前
查看原文

前置知识

解法

考虑广义圆方树。
建出广义圆方树后第二问是容易处理的。将限制条件转化为 aba \to b 是否经过 cc,即 ccLCA(a,b)\operatorname{LCA}(a,b) 的子树内且 aabbcc 的子树内。可以通过 DFS 序判断。
第一问由经典结论转化为 aba \to b 是否经过 (c,d)(c,d) 所在的点双的方点 ee(c,d)(c,d) 是割边。
  • (c,d)(c,d) 所在的方点是 c,dc,d 中深度较深的点的父亲。
  • (c,d)(c,d) 是割边等价于 ee 的度数为 22

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct node
{
	int nxt,to;
}e[1000010];
int head[100010],dfn[200010],low[100010],fa[200010],siz[200010],son[200010],top[200010],dep[200010],out[200010],du[200010],cnt=0,v_dcc=0,tot=0;
vector<int>g[200010];
stack<int>s;
void add(int u,int v)
{
	cnt++;  e[cnt]=(node){head[u],v}; head[u]=cnt;
}
void tarjan(int x)
{
	tot++;  dfn[x]=low[x]=tot;
	s.push(x);
	for(int i=head[x];i!=0;i=e[i].nxt)
	{
		if(dfn[e[i].to]==0)
		{
			tarjan(e[i].to);
			low[x]=min(low[x],low[e[i].to]);
			if(low[e[i].to]==dfn[x])
			{
				v_dcc++;
				g[v_dcc].push_back(x);  g[x].push_back(v_dcc);
				du[x]++;  du[v_dcc]++;
				int tmp=0;
				while(e[i].to!=tmp)
				{
					tmp=s.top();  s.pop();
					g[v_dcc].push_back(tmp);  g[tmp].push_back(v_dcc);
					du[tmp]++;  du[v_dcc]++;
				}
			}
		}
		else  low[x]=min(low[x],dfn[e[i].to]);
	}
}
void dfs1(int x,int father)
{
	siz[x]=1;
	fa[x]=father;
	dep[x]=dep[father]+1;
	for(int i=0;i<g[x].size();i++)
	{
		if(g[x][i]!=father)
		{
			dfs1(g[x][i],x);
			siz[x]+=siz[g[x][i]];
			son[x]=(siz[g[x][i]]>siz[son[x]])?g[x][i]:son[x];
		}
	}
}
void dfs2(int x,int id)
{
	tot++;  dfn[x]=tot;
	top[x]=id;
	if(son[x]!=0)
	{
		dfs2(son[x],id);
		for(int i=0;i<g[x].size();i++)  if(g[x][i]!=fa[x]&&g[x][i]!=son[x])  dfs2(g[x][i],g[x][i]);
	}
	out[x]=tot;
}
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;
}
bool check(int x,int y)
{
	return dfn[x]<=dfn[y]&&dfn[y]<=out[x];
}
int main()
{
// #define Isaac
#ifdef Isaac
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n,m,q,pd,u,v,x,y,rt,tmp,i;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>u>>v;
		add(u,v);  add(v,u);
	}
	v_dcc=n;
	for(i=1;i<=n;i++)  if(dfn[i]==0)  tarjan(i);
	tot=0;  dfs1(1,0);  dfs2(1,1);
	cin>>q;
	for(i=1;i<=q;i++)
	{
		cin>>pd>>u>>v>>x;
		if(pd==1)
		{
			cin>>y;  if(dep[x]>dep[y])  swap(x,y);
			tmp=fa[y];  rt=lca(u,v);
			cout<<(du[tmp]==2&&(check(rt,tmp)&&(check(tmp,u)||check(tmp,v)))?"no":"yes")<<endl;
		}
		else
		{
			rt=lca(u,v);
			cout<<((check(rt,x)&&(check(x,u)||check(x,v)))?"no":"yes")<<endl;
		}
	}
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...