CF555E Case of Computer Network

感觉不算很难。

首先边双中显然存在定向方案使其中的点互相可达。

发现缩完点双后就是一棵树，\(u\to v\) 的限制就是 \(bl_u\to lca\) 这条链上的边连向父亲，\(lca\to bl_v\) 连上连向子节点，其中 \(bl\) 表示为所在的边双编号。而这是简单的，树上差分记录一下被是否限制，如果存在矛盾就无解。

好像还有一题也是树上的这个问题，没记错的话好像可以用树剖与拓展域并查集实现。

Takanashi Rikka

// Problem: CF555E Case of Computer Network
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF555E
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define intz(x,a) memset(x,a,sizeof(x))
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
const int N=2e5+5;
vector<pii>e[N];vector<int>E[N];
struct edge{int u,v;}a[N];
int dfn[N],low[N],tot,z[N],tp,t,bl[N];bool in[N];
void solve(int v){++t;int it;do it=z[tp],in[it]=0,bl[it]=t;while(z[tp--]!=v);}
void dfs(int u,int fa){
	dfn[u]=low[u]=++tot,z[++tp]=u,in[u]=1;
	for(pii v:e[u])if(v.se^fa){
		if(!dfn[v.fi]){
			dfs(v.fi,v.se),cmn(low[u],low[v.fi]);
			if(low[v.fi]>dfn[u])solve(v.fi);	
		}else if(in[v.fi])cmn(low[u],dfn[v.fi]);
	}
	if(!fa)solve(u);
}
int lb[N],d[N],f[N],c[N][2],C[N][2];bool vis[N];
void dfs1(int u,int fa){
	d[u]=d[f[u]=fa]+1;int x=lb[fa],y=lb[x];
	lb[u]=(d[fa]-d[x]==d[x]-d[y]?y:fa);
	for(int v:E[u])if(v^fa)dfs1(v,u);
}
int lca(int x,int y){
	if(d[x]<d[y])swap(x,y);
	while(d[x]>d[y])x=(d[lb[x]]>=d[y]?lb[x]:f[x]);if(x==y)return x;
	while(x^y)(lb[x]^lb[y]?(x=lb[x],y=lb[y]):(x=f[x],y=f[y]));return x;
}
int F(int u,int x){
	while(x)
		if(d[u]-d[lb[u]]<=x)
			x-=d[u]-d[lb[u]],u=lb[u];
		else --x,u=f[u];
	return u;
}
void get(int u,int fa){
	vis[u]=1;
	for(int v:E[u])if(v^fa)get(v,u),
	C[u][0]+=C[v][0],
	C[u][1]+=C[v][1];	
}
void UesugiErii(){
	int n,m,q;cin>>n>>m>>q;
	for(int i=1,u,v;i<=m;i++)
		cin>>u>>v,a[i]={u,v},
		e[u].pb(mp(v,i)),e[v].pb(mp(u,i));
	for(int i=1;i<=n;i++)
		if(!dfn[i])dfs(i,0);
	for(int i=1,u,v;i<=m;i++)
		if(bl[u=a[i].u]^bl[v=a[i].v])
			E[bl[u]].pb(bl[v]),E[bl[v]].pb(bl[u]);
	for(int i=1;i<=t;i++)
		if(!d[i])dfs1(i,0);
	for(int u,v,lc;q;q--){
		cin>>u>>v,u=bl[u],v=bl[v],lc=lca(u,v);
		if(!lc)return cout<<"No\n",void();
		if(u!=lc)--C[lc][0],++C[u][0];
		if(v!=lc)--C[lc][1],++C[v][1];
	}
	for(int i=1;i<=t;i++)
		if(!vis[i])get(i,0);
	for(int i=1;i<=t;i++)
		if(C[i][0]&&C[i][1])return cout<<"No\n",void();
	cout<<"Yes\n";
}
signed main(){
	//cfast;
	int _=1;//cin>>_;
	for(;_;_--)UesugiErii();
	return 0;
}