题解：CF1007D Ants

题目传送门

每只蚂蚁只走一对点肯定是不劣的，由此想到 2-sat。

限制条件是：若 \((a,b)\) 和 \((c,d)\) 两条链相交，则不能同时选。直接建图肯定是爆炸的。

用树剖可以将 \((a,b)\) 这条链划分成 \(O(\log n)\) 个区间。因为同一条链的区间不交，限制条件变为若两个区间相交，则这两个点不能同时选。

把这些区间放到线段树上，限制条件变成：选了一个点，这个点在线段树上的祖先（包括自己）上的其他点都不能选。

先连左右儿子，再类似 这题 的前缀优化建图，可以满足线段树上一个区间上的点最多选一个。

具体来说记 \(f_{x, 1 \dots k}\) 表示 \(x\) 点上的前缀或，\(x\) 的左右儿子为 \(ls,rs\)，\(x\) 上挂了 \(a_1,a_2 \dots a_k\)。

1. 将 \(f_{ls,k},f_{rs,k}\) 向 \(f_{x,0}\) 连边。
2. 连边 \(f_{x,i-1}\) 和 \(f_{x,i}\)，\(f_{x,i-1}\) 和 \(\lnot a_i\)，\(a_i\) 和 \(f_{x,i}\)，当然还要对称连边

最后跑 2-sat 就行了。

时间和空间复杂度都是 \(O(m \log^2 n)\)。

Code:

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cassert>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5e6 + 10;
int tot, n, m, top[N], son[N], sz[N], fa[N], dfn[N], dep[N];
int dfn1[N], low[N], c[N], st[N];
vector <int> e[N], pos[N];
void dfs1(int x, int pfa){
	fa[x] = pfa, dep[x] = dep[pfa] + 1, sz[x] = 1;
	for(int y : e[x]){
		if(y == pfa)
			continue;
		dfs1(y, x);
		sz[x] += sz[y];
		if(sz[son[x]] < sz[y])
			son[x] = y;
	}
}
void dfs2(int x, int pfa){
	dfn[x] = ++dfn[0], top[x] = pfa;
	if(son[x])
		dfs2(son[x], pfa);
	for(int y : e[x])
		if(y != fa[x] && y != son[x])
			dfs2(y, y);
}
void update(int id, int l, int r, int x, int y, int a){
	if(x <= l && y >= r){
		pos[id].push_back(a);
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid)
		update(2 * id, l, mid, x, y, a);
	if(y > mid)
		update(2 * id + 1, mid + 1, r, x, y, a);
}
void tarjan(int x){
	low[x] = dfn1[x] = ++dfn1[0], st[++st[0]] = x;
	for(int y : e[x]){
		if(!dfn1[y]){
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if(!c[y])
			low[x] = min(low[x], dfn1[y]);
	}
	if(dfn1[x] == low[x]){
		c[x] = ++c[0];
		while(st[st[0]] != x)
			c[st[st[0]--]] = c[0];
		st[0]--;
	}
}
void update(int x, int y, int t){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]])
			swap(x, y);
		update(1, 1, n, dfn[top[x]], dfn[x], t);
		x = fa[top[x]];
	}
	if(dfn[x] > dfn[y])
		swap(x, y);
	if(dfn[x] < dfn[y])
		update(1, 1, n, dfn[x] + 1, dfn[y], t);
}
int solve(int id, int l, int r){
	int la = 0;
	if(l != r){
		int mid = (l + r) >> 1, x = solve(2 * id, l, mid), y = solve(2 * id + 1, mid + 1, r);
		if(!x || !y)
			la = x + y;
		else{
			e[x].push_back(tot);
			e[tot ^ 1].push_back(x ^ 1);
			e[y].push_back(tot);
			e[tot ^ 1].push_back(y ^ 1);
			la = tot, tot += 2;
		}
	}
	for(int i : pos[id]){
		if(la){
			e[la].push_back(i ^ 1);
			e[i].push_back(la ^ 1);
			e[la].push_back(tot);
			e[tot ^ 1].push_back(la ^ 1);
			e[i].push_back(tot);
			e[tot ^ 1].push_back(i ^ 1);
			la = tot, tot += 2;
		}
		else
			la = i;
	}
	return la;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1, u, v; i < n; i++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 1; i <= n; i++)
		e[i].clear();
	cin >> m;
	for(int i = 1, a, b, c, d; i <= m; i++){
		cin >> a >> b >> c >> d;
		update(a, b, 2 * i);
		update(c, d, 2 * i + 1);
	}
	tot = 2 * m + 2;
	solve(1, 1, n);
	for(int i = 1; i < tot; i++)
		if(!dfn1[i])
			tarjan(i);
	for(int i = 1; i <= m; i++){
		if(c[2 * i] == c[2 * i + 1]){
			cout << "NO\n";
			return 0;
		}
	}
	cout << "YES\n";
	for(int i = 1; i <= m; i++)
		cout << 1 + (c[2 * i] > c[2 * i + 1]) << "\n";
}