This technique is from 二乗の木 DP - (iwi).

Problem

We’ll take a look at this problem E: Ribbons on Tree:

Given a tree with \(N\) nodes, count the number of ways to divide them into \(\frac{N}{2}\) pairs so that all the edges in the tree is covered by at least one simple path that connects some pair \((u,\ v)\).

Observations

1. Instead of counting the number of ways with all edges covered, count the number of ways some edge is not covered.
2. If we fix the number of edges being uncovered, and the number of ways for each of those is computable, we can do inclusion-exclusion to derive the answer.
3. To find out the number of ways that exactly \(K\) edges are uncovered, we can consider removing \(K\) edges, and there we have \(K + 1\) independent connected components.
4. Each of the components must have even number size, and in such case a component with size \(n\) will have \((n-1)(n-3)(n-5)\dots1\) ways to match. Since each component is independent, we take the product of this for all components to get the ways for this tree (with some fixed \(K\) edges being removed).
5. Instead of enumerating which edges to remove, we should be able to compute this in polynomial time with tree DP.
6. Let us fix an arbitrary node as the root for the DP. Let \(dp_{u, f, s} =\\ \text{considering subtree with root u,}\\\text{having some number with same parity of f edges removed already,}\\\text{component size of u being s,}\\\text{number of ways to match all the nodes except the ones in component of u}\)
7. From observation 4, let \(g(x) = \begin{cases} (x-1)g(x-2), & \text{if}\ 0 < x \land 2\ |\ x \\ 1, & \text{if}\ x=0 \\ 0, & \text{otherwise} \end{cases}\).
   To merge the current \(dp_u\) with some \(dp_v\) where \(v\) is a child of \(u\), we have \(new\_u_{k,r} = \sum u_{f, s} g(r-s) v_{k\oplus f\oplus 1, r-s} + \sum u_{f, s} v_{k\oplus f, r-s}\) (which is basically to cut or not to cut).

Complexity Analysis

The transition in observation 7 looks like some polynomial multiplication for each node.

For the sake of simplicity, consider a node with two subtrees to merge. The left having size \(L\), the other size \(R\). Let the complexity of merging such node be \(T(n)\), we would have \(T(L + R) = T(L) + T(R) + O(LR)\). To analyze the upperbound of \(T\), we can consider the fact that \((L + R)^2 = L^2 + R^2 + 2LR\), thus putting \(T(n) = O(n^2)\) makes sense as \(O((L + R)^2) = O(L^2) + O(R^2) + O(LR)\).

Furthermore, this identity holds for any number of terms, which makes the algorithm work in \(O(n^2)\) no matter how many subtrees are to be merged at any node.

Code

#include <bits/stdc++.h>
using namespace std;

const int M = int(1e9 + 7);

using vec = vector<int>;
using mat = vector<vec>;
using cub = vector<mat>;

signed main() {
  int N;
  cin >> N;

  mat G(N);
  for (int i = 0; i + 1 < N; ++i) {
    int X, Y;
    cin >> X >> Y;
    G[X - 1].emplace_back(Y - 1);
    G[Y - 1].emplace_back(X - 1);
  }

  vec g(N + 1);
  g[0] = 1;
  for (int i = 2; i < g.size(); i += 2) g[i] = 1LL * g[i - 2] * (i - 1) % M;

  cub dp(N, mat(2));
  function<void(int, int)> dfs = [&](int u, int fa) {
    dp[u] = { {0, 1}, {0, 0} };
    for (int v : G[u]) {
      if (v == fa) continue;
      dfs(v, u);
      mat w(2, vec(dp[u][0].size() + dp[v][0].size() - 1));
      for (int f = 0; f < 2; ++f)
        for (int s = 1; s < dp[u][0].size(); ++s)
          for (int h = 0; h < 2; ++h)
            for (int t = 1; t < dp[v][0].size(); ++t) {
              (w[f ^ h ^ 1][s] +=
                1LL * dp[u][f][s] * g[t] % M * dp[v][h][t] % M
              ) %= M;
              (w[f ^ h][s + t] += 1LL * dp[u][f][s] * dp[v][h][t] % M) %= M;
            }
      swap(w, dp[u]);
    }
  };

  dfs(0, -1);

  int ans = 0;
  for (int i = 0; i < 2; ++i)
    for (int j = 1; j <= N; ++j)
      (ans += (i == 0 ? 1LL : -1LL) * dp[0][i][j] * g[j] % M) %= M;

  if (ans < 0) ans += M;
  cout << ans << endl;

  return 0;
}