AGC029F

题意

给定(n-1)个({1,2,...,n})的子集(E_i)（(E_ige 2)），每个子集选择两个点连边，使得最后形成一棵树。

做法

考虑二分图：(ulongrightarrow id(i)(uin E_i))

假设我们得到了解，观察其在二分图上的样子是怎样的？

对于(E_i)，选出来的为((u,v))，二分图上选出((u,i)(v,i))。
由于最终构成了一棵树，对于任意右侧集合(S)，选出的左边的点集并大小(ge |S|+1)。（1）

这等价于，若我们删去左侧任意节点，那么对于右侧集合(S)，选出的左边的点集并(ge |S|)。
根据( ext{hall})定理，此时((n-1)-(n-1))二分图有完美匹配。

那么我们先网络流跑一遍完美匹配，如果不存在完美匹配显然不合法。
注意，若存在完美匹配，不一定合法，因为不一定满足（1）。

我们假设满足（1），可以构造一组解：

以(1)为根( ext{dfs})。
每次遍历(u)所在的(E_i)（集合(i)还没有访问过），然后继续往(i)的匹配边的点( ext{dfs})。
如果满足(N(S)ge |S|+1)，那么一定能找到(i)。
假设现在已经用过了(T)集合，(T不为全集)，无法在已经遍历的点找到另外的集合，那么(N(U-T)le |U-T|)，与假设不符。（其中(U)为({1,2,ldots,n-1})即全集）