【Codeforces 1007D】Ants
mrsrz
4月 01, 2020
树剖线段树分治前缀优化建图 2-SAT。
题目大意：
给定一棵 $n$ 个点的树，有 $m$ 只蚂蚁，第 $i$ 只蚂蚁有参赛 $a_i,b_i,c_i,d_i$。
现在，每只蚂蚁可以选择是从 $a_i$ 到 $b_i$ 还是从 $c_i$ 到 $d_i$。
要求输出一种蚂蚁的选择方案，使得一条路径只被一只蚂蚁经过。
题解：
二选一的问题，容易想到 2-SAT。
直接连边是 $O(m^2)$ 的，无法接受，考虑优化连边。
对树进行树链剖分，然后在 dfs 序上进行线段树分治。
对每条路径，将其拆成 $O(\log^2n)$ 条 dfs 序上的连续段。
考虑递归遍历这棵线段树，并用栈保存当前的路径。
一条路径入栈的时候，栈中的其它路径和它，只能选择 $1$ 条。
这就可以用到一个比较经典的优化建图方法了。每个点入栈的时候，新增一对点，表示这条路径及其之前的路径中，是否已经选了一条了。
由于这是一个栈，所以每次入栈的路径对应的前一个点是唯一的。
然后我们就有 $O(m\log^2 n)$ 个点和边。用 Tarjan 求解 2-SAT 即可。
时空复杂度 $O(n+m\log^2 n)$。
Code：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=114514,M=8000005;
struct edge{
int to,nxt;
}e[N<<1];
int head[N],fa[N],son[N],cnt,n,dfn[N],top[N],idx,sz[N],dep[N],idfn[N],m;
struct info{
int u1,v1,u2,v2;
}A[N];
namespace Graph{
edge e[M];
int nod,dfn[M],idx,head[M],cnt,low[M],sta[M],SCC,bel[M],top;
bool vis[M];
inline void addedge(int u,int v){e[++cnt]=(edge){v,head[u]},head[u]=cnt;}
void dfs(int now){
vis[now]=1,sta[++top]=now;
dfn[now]=low[now]=++idx;
for(int i=head[now];i;i=e[i].nxt)
if(!dfn[e[i].to])dfs(e[i].to),low[now]=min(low[now],low[e[i].to]);else
if(vis[e[i].to])low[now]=min(low[now],dfn[e[i].to]);
if(low[now]==dfn[now]){
++SCC;
int v;
do{
v=sta[top--];
bel[v]=SCC;
vis[v]=0;
}while(v!=now);
}
}
void work(){
for(int i=1;i<=nod;++i)if(!dfn[i])dfs(i);
for(int i=1;i<=m;++i)if(bel[i]==bel[i+m])return void(puts("NO"));
for(int i=m*2+1;i<=nod;i+=2)if(bel[i]==bel[i+1])return void(puts("NO"));
puts("YES");
for(int i=1;i<=m;++i)puts(bel[i]<bel[i+m]?"1":"2");
}
}
void dfs(int now){
sz[now]=1;
for(int i=head[now];i;i=e[i].nxt)
if(!dep[e[i].to]){
dep[e[i].to]=dep[now]+1,fa[e[i].to]=now,dfs(e[i].to);
sz[now]+=sz[e[i].to];
if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
}
}
void dfs2(int now){
idfn[dfn[now]=++idx]=now;
if(son[now])top[son[now]]=top[now],dfs2(son[now]);
for(int i=head[now];i;i=e[i].nxt)
if(e[i].to!=son[now]&&dep[e[i].to]>dep[now])dfs2(top[e[i].to]=e[i].to);
}
vector<int>vec[N<<2];
void add_(int l,int r,int o,const int&L,const int&R,const int&v){
if(L>R)return;
if(L<=l&&r<=R)vec[o].push_back(v);else{
const int mid=l+r>>1;
if(L<=mid)add_(l,mid,o<<1,L,R,v);
if(mid<R)add_(mid+1,r,o<<1|1,L,R,v);
}
}
inline int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])x^=y^=x^=y;
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void add(int x,int y,int id){
int t=LCA(x,y);
bool b=1;
deb:
while(top[x]!=top[t]){
add_(1,n,1,dfn[top[x]],dfn[x],id);
x=top[x];
if(fa[x]==t)break;
x=fa[x];
}
if(top[x]==top[t]&&x!=t)add_(1,n,1,dfn[t]+1,dfn[x],id);
if(b){x=y,b=0;goto deb;}
}
pair<int,int>sta[N];int tp;
void solve(int l,int r,int o){
int TOP=tp;
for(int id:vec[o]){
pair<int,int>&nw=sta[tp+1];
nw.first=++Graph::nod,nw.second=++Graph::nod;
int _1=id,_0=id>m?id-m:id+m;
if(tp){
Graph::addedge(sta[tp].first,nw.first),
Graph::addedge(nw.second,sta[tp].second);
Graph::addedge(sta[tp].first,_0);
Graph::addedge(_1,sta[tp].second);
}
Graph::addedge(_1,nw.first),Graph::addedge(nw.second,_0);
++tp;
}
if(l<r){
const int mid=l+r>>1;
solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
}
tp=TOP;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
e[++cnt]=(edge){u,head[v]},head[v]=cnt;
}
dfs(dep[1]=1),dfs2(top[1]=1);
scanf("%d",&m);
Graph::nod=m*2;
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&A[i].u1,&A[i].v1,&A[i].u2,&A[i].v2);
add(A[i].u1,A[i].v1,i);add(A[i].u2,A[i].v2,i+m);
}
solve(1,n,1);
Graph::work();
return 0;
}