\(\mathcal{Description}\)

  Link.

  指定一棵大小为 \(n\)，以 \(1\) 为根的有根树的 \(m\) 对邻接关系与 \(q\) 组 \(\text{LCA}\) 关系，求合法树的个数。

  \(0\le m<n\le13\)，\(q\le100\)。

\(\mathcal{Solution}\)

  巧妙的状压 owo。不考虑限制，自然地有状态 \(f(u,S)\) 表示用 \(S\) 中的结点构成以 \(u\) 为根的树的方案数。转移相当于划分出一棵子树，有：

\[f(u,S)=\sum_{v\in T\subseteq(S\setminus u)}f(v,T)f(u,S-T)
\]

  不过这样显然会算重复。考虑任意固定子树 \(T\) 内的某个点，设 \(p\not=u\) 且 \(p\in T\)，钦定 \(p\in T\) 就避免了重复，则：

\[f(u,S)=\sum_{v,p\in T\subseteq(S\setminus u)}f(v,T)f(u,S-T)
\]

  注意 \(p\) 在求和过程中是常量。

---

  接下来着手处理限制：

• 限制 \(\text{LCA}\)，设当前状态 \(f(w,S)\)，枚举到子集 \(T\)：

  • 若 \((u\in T)\land(v\in T)\Leftrightarrow\mathrm T\)（注意最后这个罗马字体的 \(\mathrm T\) 表示逻辑运算为真），\(u\) 和 \(v\) 的 \(\text{LCA}\) 必然在 \(T\) 中，所以必然不是 \(w\)，矛盾。
  • 若 \(q,r\) 的 \(\text{LCA}\) 指定为 \(p\)，且 \(p\in T\land(q\not\in T\lor q\not\in T)\Leftrightarrow \mathrm T\)，即两点的 \(\text{LCA}\) 深于其中至少一个点，显然不满足。

• 限制邻接点，同样地设当前状态 \(f(w,S)\)，枚举到子集 \(T\)：

  • 若 \(u,v\not=r\) 邻接，且 \((u\in T)\leftrightarrow(v\in T)\Leftrightarrow\mathrm F\)，即有且仅有其中一点属于 \(T\)，矛盾。

  • 若 \(u,v\) 均与 \(w\) 邻接，且 \((u\in T)\land(v\in T)\Leftrightarrow\mathrm T\)，即 \(w\) 向子树 \(T\) 内的至少两个点连边，矛盾。

      转移的时候判一下这四种情况就行啦。

      复杂度 \(\mathcal O(3^nn(n+m+q))\)，不过跑不满。为什么我交一发当场最优解 rank1 呢 www？

  #include
  #include
  #include

  #define bel( x, S ) ( ( S >> x ) & 1 )

  typedef long long LL;
  typedef std::pair pii;

  const int MAXN = 13;
  int n, m, q;
  LL f[MAXN + 5][1 << MAXN]; std::vector adj[MAXN + 5];
  std::vector dif[MAXN + 5];

  inline bool check ( const int r, const int T ) {
  for ( pii p: dif[r] ) { // LCA情况1.
  if ( bel ( p.first, T ) && bel ( p.second, T ) ) {
  return false;
  }
  }
  for ( int u = 0; u < n; ++ u ) { // LCA情况2. if ( ! ( ( T >> u ) & 1 ) ) continue;
  for ( pii p: dif[u] ) {
  if ( ! bel ( p.first, T ) || ! bel ( p.second, T ) ) {
  return false;
  }
  }
  }
  for ( int u = 0; u < n; ++ u ) { // 邻接情况1.
  if ( u == r ) continue;
  for ( int v: adj[u] ) {
  if ( v ^ r && bel ( u, T ) ^ bel ( v, T ) ) {
  return false;
  }
  }
  }
  int cnt = 0;
  for ( int u: adj[r] ) cnt += bel ( u, T ); // 邻接情况2.
  return cnt <= 1;
  }

  inline LL solve ( const int r, int S ) {
  LL& ret = f[r][S];
  if ( ~ ret ) return ret;
  ret = 0, S ^= 1 << r; // 这里注意去除根节点. int p; for ( p = 0; p < n && ! ( ( S >> p ) & 1 ); ++ p ); // 钦定一点p.
  for ( int T = S; T; T = ( T - 1 ) & S ) { // 枚举子集.
  if ( ! ( ( T >> p ) & 1 ) || ! check ( r, T ) ) continue;
  for ( int u = 0; u < n; ++ u ) {
  if ( ! bel ( u, T ) ) continue;
  ret += solve ( u, T ) * solve ( r, S ^ T ^ ( 1 << r ) );
  }
  }
  return ret;
  }

  int main () {
  scanf ( "%d %d %d", &n, &m, &q );
  for ( int i = 1, u, v; i <= m; ++ i ) {
  scanf ( "%d %d", &u, &v ), -- u, -- v;
  adj[u].push_back ( v ), adj[v].push_back ( u );
  }
  for ( int i = 1, u, v, w; i <= q; ++ i ) {
  scanf ( "%d %d %d", &u, &v, &w ), -- u, -- v, -- w;
  dif[w].push_back ( { u, v } );
  }
  memset ( f, 0xff, sizeof f );
  for ( int u = 0; u < n; ++ u ) f[u][1 << u] = 1; // 单点，一种方案.
  printf ( "%lld\n", solve ( 0, ( 1 << n ) - 1 ) );
  return 0;
  }