专栏文章
P4334 [COI 2007] Policija 题解
P4334题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mipuhw0t
- 此快照首次捕获于
- 2025/12/03 18:09 3 个月前
- 此快照最后确认于
- 2025/12/03 18:09 3 个月前
前置知识
解法
考虑广义圆方树。
建出广义圆方树后第二问是容易处理的。将限制条件转化为 是否经过 ,即 在 的子树内且 或 在 的子树内。可以通过 DFS 序判断。
第一问由经典结论转化为 是否经过 所在的点双的方点 且 是割边。
- 所在的方点是 中深度较深的点的父亲。
- 是割边等价于 的度数为 。
代码
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 条评论,欢迎与作者交流。
正在加载评论...