题解 CF1254E 【Send Tree to Charlie】
CYJian
2020-03-25 10:00:59
这个题，算是思路好想细节很多的题的典型...不过比起其他的相同类型的题来说，这个题好写一些就是了...
先想想大致做法：我们发现，对于一个点，只要其所有出边的相对顺序确定了，其最终局面就可以确定了。
然后对于一个「钦定数字 $x$ 出现在位置 $i$ 上」的限制，我们可以转化成如下的一些限制条件：
- 编号为 $x$ 的点第一个被删除的边是谁。
- 编号为 $i$ 的点最后一个被删除的边是谁。
- $x$ 到 $i$ 的链上，相邻两条边中（钦定靠近 $x$ 的是 $A$，另一个为 $B$）$A$ 被删除之后，$B$ 需要立即被删除。（可以看做是边 $A$ 向边 $B$ 连了一条有向边）
然后注意到，这种删边的顺序，在互不冲突的情况下，至多只能加入 $O(n)$ 级别的限制条件。那么我们只需要每次暴力扫 $x$ 到 $i$ 的链，然后判断加入限制条件后是否会导致不合法就行了。
然后我们来仔细分析不合法的若干情况：
- $x$（$x \ge 0$）在给出的 $a$ 序列中出现两次以上，一定不合法；解决方案：开个桶记录一下就行了。
- 限制条件成环，一定不合法；解决方案：并查集维护一下限制条件连成的链集合即可。
- 当一个点的所有出边中，第一个和最后一个被删除的边连成了链，且这个点还存在其他边不在这条链上（或者说，这个点的限制连成的链数 $\ge 2$），则一定不合法；解决方案：判断起点和终点是否在一个链集合中，如果在就判断链数。
如果不存在不合法的情况，则需要求出满足限制的方案数。这个方案数非常好求，只需要求出每个点的限制条件连出的链数（记为 $S_i$），则最后的方案数即为：$\prod_{i=1}^{n}S_i!$。
$\rm Code$：
```cpp
const int MAXN = 500010;
const int mod = 1e9 + 7;
int n, flag;
int tot = 1;
int fi[MAXN];
int deg[MAXN]; // 初始限制条件连出链数即为度数，所以用了 deg 表示链数
int ne[MAXN << 1];
int to[MAXN << 1];
inline void Link(int u, int v) {
tot++;
++deg[u];
to[tot] = v;
ne[tot] = fi[u];
fi[u] = tot;
}
int st[MAXN];
int ed[MAXN]; // 记录每个点的第一个和最后一个被删除的边
int fa[MAXN];
int vis[MAXN]; // 桶
int fac[MAXN];
int dep[MAXN];
int tof[MAXN]; // 记录每个点的父边编号
int L[MAXN << 1];
int R[MAXN << 1];
int f[MAXN << 1];
inline int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
inline int Merge(int x, int y) { return x = find(x), y = find(y), x == y ? 1 : (f[x] = y, 0); }
inline void dfs(int x, int la) {
dep[x] = dep[la] + 1, fa[x] = la;
for(int i = fi[x]; i; i = ne[i]) {
int u = to[i];
if(u == la) { tof[x] = i; continue; }
dfs(u, x);
}
}
inline void Solve(int u, int v) {
queue<int>q; stack<int>s; int St = u, Ed = v;
while(dep[u] > dep[v]) --deg[u], q.push(tof[u]), u = fa[u];
while(dep[u] < dep[v]) --deg[v], s.push(tof[v]), v = fa[v];
while(u != v) {
--deg[u], q.push(tof[u]), u = fa[u];
--deg[v], s.push(tof[v]), v = fa[v];
} --deg[u]; // 以上工作为，扫出路径上的边，并且由于每个点上的限制都多了一，则不考虑不合法的情况下链数都会 -1
while(!s.empty()) q.push(s.top() ^ 1), s.pop();
int las = q.front(); q.pop();
if(st[St] || L[las]) flag = 1; // 如果这条边已经钦定了一个在其之后删除的边，或者这个点已经有了第一个被删除的边，则不合法。函数中其他的判断类似。
st[St] = las, L[las] = -1;
while(!q.empty()) {
int x = q.front(); q.pop(), las ^= 1;
if(R[las] || L[x] || Merge(x, las)) flag = 1;
L[x] = las, R[las] = x, las = x;
} las ^= 1;
if(ed[Ed] || R[las]) flag = 1;
ed[Ed] = las, R[las] = -1;
}
int main() {
n = ri, fac[0] = 1;
for(int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % mod;
for(int i = 1; i < n; i++) {
int u = ri, v = ri;
Link(u, v), Link(v, u);
} dfs(1, 0);
for(int i = 2; i <= tot; i++) f[i] = i;
for(int i = 1; i <= n; i++) {
int x = ri; // x --> i
if(!x) continue;
if(vis[x] || x == i) { flag = 1; break; }
vis[x] = 1, Solve(x, i);
if(flag) break;
} int res = !flag;
for(int i = 1; i <= n; i++) {
if(st[i] && ed[i]) {
if(find(st[i]) != find(ed[i])) res = 1LL * res * fac[deg[i]] % mod;
else res *= deg[i] == -1; // 由于「钦定一条边是第一个/最后一个删除」这个限制条件也会令排列中可自由选择位置的链 -1，所以我也让这种情况的 deg-1 了。所以在知道了既有开头也有结尾的情况下，链数为一等价于 deg=-1。
} else res = 1LL * res * fac[deg[i]] % mod;
} cout << res << endl;
return 0;
}
```