LOJ571 Misaka Network 与 Accelerator 题解
2-SAT+线段树优化建图+边分治
Statement
给定一棵 \(n\) 个点的树，\(m\) 条限制和区间 \([L,R]\)。你需要选出 \(n\) 个点的一个子集（可以为空或者全集），满足给出的所有限制。
每条限制形如：若 \(u\) 点（被选了/没被选），则树上与 \(u\) 距离在 \([L,R]\) 间的点都（被选了/没被选）
问是否有解。
\(1≤n,m,L,R≤5×10^4\)
Solution
搞了一晚上+半个上午。。。
看到这种限制方式，我们容易想到 2-SAT
看到一个点向多个点连边，我们可以想到线段树优化建图，直接套用 CF786B Legacy 的做法，开两个线段树 \(TreeIn,TreeOut\) 连边。
考虑的是到点 \(u\) 的距离在 \([L,R]\) 之内的点，关于树上路径长度，我们可以想到点分治（联想地，如果题面把“树上与 \(u\) 距离”改成子树内的点，我们可以使用 bfs 序）
但由于淀粉质涉及到多个子树之间，不好合并，我们不妨使用边分治
对于每一个分治边，我们对于边两端的子树分别建立起“动态开点权值线段树”，权值为点的深度
在线段树的叶子节点，我们再挂上对应深度的点具体是什么
注意由于我们要跑 2-SAT ，所以每一个点还要拆成两个，这里的处理方式是再来一棵线段树
对于一个左部点，我们根据限制条件的类型连边右部的线段树即可
这样我们有 \(O(\log )\) 个分治边，建立起来了 \(O(\log)\) 棵线段树，复杂度 \(O(n\log^2n)\)
然后就这样硬写，写完之后蒟蒻傻不拉几地盯着看了半天调不动，下面的代码仅作示意&纪念 （快略过）
//算空间真烦！
//双向边两倍空间，三度化两倍，线段树空间四倍,两棵8倍
#include
#define ls lc[rt]
#define rs rc[rt]
#define mid ((l+r)>>1)
// #define id(rt,op,k) ((k-1)*(N<<2)+rt+K*op)
// 点 rt,在 op(0/1)In/Out 中，第 k 棵树
#define ori(i,op) (M+n*op+i)
/*
0 [1,n] 为在 TreeIn 中点的选择点
1 [n+1,2n] 为在 TreeOut 中点的选择点
2 [2n+1,3n] 为在 TreeIn 中点的不选择点
3 [3n+1,4n] 为在 TreeOut 中点的不选择点
*/
#define Go(E,u) for(int e=E.head[u],v;v=E.edge[e].to,e;e=E.edge[e].nex)
using namespace std;
const int N = 5e4+5;
const int M = 2e6;
const int K = 1e6;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){;
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
bool cmin(int &a,int b){return a>b?a=b,1:0;}
bool cmax(int &a,int b){return aitem[N],Edge[M];
int leaf[75][N],lc[M],rc[M];
int dep[2][N],siz[N],rot[75],p[N],mxd[2];
int id[N<<1][2][75],ori[N][4];
int dfn[M],low[M],stk[M],scc[M];
int n,m,tot,L,R,cnt,rt0,rt1,bd,mxp,S,tim,top;
int ll,rr,pos,op,k;//parameters of connect(l,r,rt,k)/connect(u,fath,o)
bool vis[N<<2],pd[M];
void rebuild(int u,int fath){
int f=0;
Go(E,u)if(v^fath){
if(!f)G.addedge(u,v,1),f=u;
else ++tot,G.addedge(f,tot,0),G.addedge(tot,v,1),f=tot;
rebuild(v,u);
}
}
void build(int l,int r,int& rt,int k){
if(!rt)rt=++S,id[rt][0][k]=S,id[rt][1][k]=S+K;
if(l==r)return leaf[k][l]=rt,void();
build(l,mid,ls,k),build(mid+1,r,rs,k);
Edge[id[rt][0][k]].emplace_back(id[ls][0][k]),Edge[id[rt][0][k]].emplace_back(id[rs][0][k]);
Edge[id[ls][1][k]].emplace_back(id[rt][1][k]),Edge[id[rs][1][k]].emplace_back(id[rt][1][k]);
}
void connect(int l,int r,int rt,int k){
if(ll<=l&&r<=rr){
if(op)Edge[id[rt][op][k]].emplace_back(pos);//区间连单点 Out连In
else Edge[pos].emplace_back(id[rt][op][k]);//单点连区间 Out连In
return ;
}
if(ll<=mid)connect(l,mid,ls,k);
if(mid 然后学习了 的优雅代码，并自己写了一发
为了处理每个点选和不选拆出的两种点，这里依旧是拆成了两颗线段树，不过写在了一起
即设 \(id[rt][0/1]\) 记录线段树上节点 \(rt\) 所对应的深度区间 全不选/全选 的情况的点
那么，每个结点和它的两个儿子连边 \(id[rt][0/1]\to id[ls][0/1],id[rt][0/1]\to id[rs][0/1]\)
\(ls,rs\) 表示左右孩子，这里的 \(\to\) 是按照 2-SAT 的方式连边，即同时连了 \((u,v)\) 和 \((!v,!u)\) （\(!u\) 表示 \(u\) 的反面）
对于当前边分治的分治中心边 \(bd\) 管辖范围内的每个结点 \(x\) (\(x\) 代表接入了该结点,\(!x\) 代表不接入该结点)，设它到边 \(bd\) 的该侧端点的距离为 \(dep\)，我们就把 \(x\) 和线段树上 \(dep\) 对应的叶子节点 \(rt\) 连边 \(id[rt][0]\to !x,id[rt][1]\to x\)
并与另一侧线段树上深度范围在 \([L-dep-edge[bd].dis,R-d-edge[bd].dis]\) 内的结点 \(rt\) 按题目给的要求连边 \(\{x\to id[rt][0],x\to id[rt][1],!x\to id[rt][0],!x\to id[rt][1]\}\)
最后跑2-SAT就行了，值得注意的是，这里不宜使用 tarjan 求强连通分量，因为要开 \(4\) 个数组，内存有点紧
这里就直接暴力枚举起点扫荡全图，如果扫到点 \(x\) 的时候发现 \(!x\) 也被扫过，那就 G 了
一个连通块只需要扫一次，所以这样是 \(O(n)\) 的
Code
#include
#define ls lc[rt]
#define rs rc[rt]
#define mid ((l+r)>>1)
#define pii pair
#define scan() for(int e=head[u],v;v=edge[e].to,~e;e=edge[e].nex)
#define scanG() for(int e=H[u],v;v=G[e].to,~e;e=G[e].nex)
using namespace std;
const int N = 2e5+5;
const int inf = 1e9;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
bool cmin(int &a,int b){return a>b?a=b,1:0;}
bool cmax(int &a,int b){return a=L)connect1(l,mid,ls,L,R,v,f,op),connect1(mid+1,r,rs,L,R,v,f,op);
}
void connect2(int l,int r,int rt,int cur,int v){
if(l==r){
ts.addedge(id[rt][0],v,1,0);
ts.addedge(id[rt][1],v,1,1);
return ;
}
cur<=mid?connect2(l,mid,ls,cur,v):connect2(mid+1,r,rs,cur,v);
}
}seg;
struct Edge{int nex,to,dis;}edge[N],G[N];
int head[N],H[N],a[N],siz[N],dep[N],rot[N],Mxd[N];
int n,m,elen,glen,tot,bd,mxp,mxd,L,R;
bool vis[N];
void addedge(int u,int v){
edge[elen]=(Edge){head[u],v,0},head[u]=elen++;
edge[elen]=(Edge){head[v],u,0},head[v]=elen++;
}
void addedge(int u,int v,int w){
G[glen]=(Edge){H[u],v,w},H[u]=glen++;
G[glen]=(Edge){H[v],u,w},H[v]=glen++;
}
void rebuild(int u,int fath){
int f=0;
scan()if(v^fath){
if(!f)addedge(u,v,1),f=u;
else ++tot,addedge(f,tot,0),addedge(tot,v,1),f=tot;
rebuild(v,u);
}
}
void getroot(int u,int fath,int tot){
siz[u]=1;
scanG()if(v!=fath&&!vis[e]){
getroot(v,u,tot),siz[u]+=siz[v];
if(cmin(mxp,max(siz[v],tot-siz[v])))bd=e;
}
}
void getdep(int u,int fath){
mxd=max(mxd,dep[u]);
scanG()if(v!=fath&&!vis[e])
dep[v]=dep[u]+G[e].dis,getdep(v,u);
}
void construct(int u,int fath,int k){
seg.connect2(0,Mxd[k],rot[k],dep[u],seg.ori[u]);
for(int i=0;i<=3;++i)if(a[u]>>i&1)
seg.connect1(0,Mxd[k^1],rot[k^1],L-dep[u]-G[k^1].dis,R-dep[u]-G[k^1].dis,seg.ori[u],i>>1&1,i&1);
scanG()if(v!=fath&&!vis[e])construct(v,u,k);
}
void divide(int u,int tot){
if(tot==1)return;
mxp=inf,getroot(u,0,tot);
vis[bd]=vis[bd^1]=true;
mxd=dep[G[bd].to]=0,getdep(G[bd].to,0),seg.build(0,Mxd[bd]=mxd,rot[bd]);
mxd=dep[G[bd^1].to]=0,getdep(G[bd^1].to,0),seg.build(0,Mxd[bd^1]=mxd,rot[bd^1]);
construct(G[bd].to,0,bd),construct(G[bd^1].to,0,bd^1);
int a=siz[G[bd].to],b=tot-siz[G[bd].to],t=bd;
divide(G[t].to,a),divide(G[t^1].to,b);
}
signed main(){
memset(head,-1,sizeof(head)),memset(H,-1,sizeof(H));
n=tot=read(),m=read(),L=read(),R=read();
for(int i=1,u,v;i