2017 TCO Round 3A Division I Hard, HiddenRabbits

题目大意

给定一棵 $n$ 个节点的无根树。
你需要构造一个函数 $f:[m]\rightarrow T$ 满足若干个形如 $(r_i,a_i,b_i,x_i)$ 的限制。
一个限制表示当 $r_i$ 为根的时候,$\operatorname{LCA}\left(f(a_i),f(b_i)\right)=x_i$。

$2\leq n\leq251,2\leq m\leq 250$
限制的个数 $\leq 250$


题目分析

定义 $F_{x,y,z}$ 表示 $f(z)$ 是否在有向边 $(x,y)$ 的子树内。显然 $F_{x,y,z}$ 和 $F_{y,x,z}$ 共同构成了一个布尔变量。
根据树的形态我们可以得到 $F_{y,z,p}\rightarrow F_{x,y,p}$。
至于限制的要求,首先 $f(a_i)$ 和 $f(b_i)$ 得都在 $x_i$ 子树内,即 $F_{fa_{x_i},x_i,a_i}=1$ 以及 $F_{fa_{x_i},x_i,b_i}=1$。
其次,它们得属于不同子树,即 $\forall (x_i,y)\in E,y\neq fa_{x_i},F_{x_i,y,a_i} \land F_{x_i,y,b_i}=0$。
跑一遍 2-SAT 即可出解。
时间复杂度 $O(mn^2)$ 吧大概。


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>

using namespace std;

const int N=251;
const int M=250;
const int Q=250;
const int V=M*(N-1<<1);
const int E=1000000;

typedef pair<int,int> data;
#define mkp(a,b) make_pair(a,b)
#define ft first
#define sd second

int bel[V],DFN[V],low[V],last[V],deg[V],rev[V],nd[V];
bool chosen[V],vis[V],exist[V];
int fa[N][N],fe[N][N];
vector<data> edge[N];
int edge_tmp[E][2];
int nxt[E],tov[E];
int n,v,tot,idx,scc_cnt;
vector<int> ans;
stack<int> st;
queue<int> q;

inline int node(int x,int eid){return (x*(n-1)<<1)+eid;}

inline void insert(int x,int y,bool rec=1)
{
tov[++tot]=y,nxt[tot]=last[x],last[x]=tot;
if (rec) edge_tmp[tot][0]=x,edge_tmp[tot][1]=y;
}

void dfs(int x,int *fa,int *fe){for (data e:edge[x]) if (e.ft!=fa[x]) fa[e.ft]=x,fe[e.ft]=e.sd,dfs(e.ft,fa,fe);}

void tarjan(int x)
{
DFN[x]=low[x]=++idx,st.push(x),exist[x]=1;
for (int i=last[x],y;i;i=nxt[i])
if (!DFN[y=tov[i]]) tarjan(y),low[x]=min(low[x],low[y]);
else if (exist[y]) low[x]=min(low[x],DFN[y]);
if (DFN[x]==low[x])
{
int y;
do{bel[y=st.top()]=scc_cnt,st.pop(),exist[y]=0;}while (x!=y);
nd[scc_cnt++]=x;
}
}

void floodfill(int x)
{
if (vis[x]) return;
vis[x]=chosen[x]=1;
for (int i=last[x];i;i=nxt[i]) floodfill(tov[i]);
}

void two_sat()
{
for (int x=0;x<scc_cnt;++x) if (!deg[x]) q.push(x);
for (int x;!q.empty();)
{
x=q.front(),q.pop();
if (!vis[x]) vis[x]=1,chosen[x]=0,floodfill(bel[nd[x]^1]);
for (int i=last[x],y;i;i=nxt[i])
if (!--deg[y=tov[i]]) q.push(y);
}
}

class HiddenRabbits
{
public:
vector <int> whereAreTheRabbits(vector <int> p, int m, vector <int> r, vector <int> a, vector <int> b, vector <int> x)
{
n=(int)p.size()+1;
for (int i=1;i<n;++i) edge[i].push_back(mkp(p[i-1],i-1<<1)),edge[p[i-1]].push_back(mkp(i,i-1<<1|1));
for (int x=0;x<n;++x) fa[x][x]=-1,dfs(x,fa[x],fe[x]);
v=m*(n-1<<1);
for (int i=0;i<m;++i)
for (int x=0;x<n;++x)
for (data e:edge[x])
for (data e_:edge[e.ft])
{
if (e_.ft==x) continue;
int p=node(i,e.sd),q=node(i,e_.sd);
insert(q,p);
}
for (int i=0;i<(int)r.size();++i)
{
if (r[i]!=x[i])
{
int e=fe[r[i]][x[i]],p=node(a[i],e),q=node(b[i],e);
insert(p^1,p),insert(q^1,q);
}
for (data e:edge[x[i]])
{
if (e.ft==fa[r[i]][x[i]]) continue;
int p=node(a[i],e.sd),q=node(b[i],e.sd);
insert(p,q^1),insert(q,p^1);
}
}
idx=0;
for (int x=0;x<v;++x) if (!DFN[x]) tarjan(x);
int tot_=tot;
for (int x=0;x<v;++x) last[x]=0;
for (;tot;nxt[tot--]=0);
for (int i=1,x,y;i<=tot_;++i) if ((x=bel[edge_tmp[i][0]])!=(y=bel[edge_tmp[i][1]])) insert(x,y,0),++deg[y];
for (int x=0;x<v;x+=2) if (bel[x]==bel[x^1]) return vector<int>();
two_sat();
for (int i=0,x;i<m;++i)
{
x=0;
for (bool found=1;found;)
{
found=0;
for (data e:edge[x])
if (e.ft!=fa[0][x])
if (chosen[bel[node(i,e.sd)]])
{
x=e.ft,found=1;
break;
}
}
ans.push_back(x);
}
return ans;
}
};