Codeforces 1078C. Vasya and Maximum Matching (Tree+DP)

日付: 11月 20, 2018

[Problem - 1078C - Codeforces](https://codeforces.com/contest/1078/problem/C)

## Problem
Given a tree, calculate how many ways to delete some subset of edges such that the maximum matching of the remaining part is unique.

**Constraints**: $1\le n \le 3\cdot 10^5$

## Solution
Apparently this is a tree dp problem. But the state-transition equation is very complicated and hard to think of.

Firstly, it is quite easy to observe that, to make the maximum matching unique, a node can have **at most one edge** connecting to its children. And to make the matching maximum, it must be also perfect (i.e. every vertex with incident edges must be matched). Then for each node, we will iterate on which edge is remained and whether it is used in the matching, keeping the matching perfect. Now begin the dp, lets define the dp variables:
* $f_{u,0}$ - The answer of subtree with root $u$, i.e. the number of ways to delete edges in this subtree to make it valid.
* $f_{u,1}$ - The number of ways to make subtree with root $u$ valid, but $u$ must be matched to one of its children.
* $f_{u,2}$ - The number of ways to make subtree with root $u$ valid, but $u$ **must be matched to its parent (if it has a parent)**. This is for the situation that $u$ and one child of $u$ has edge connected but this edge is not used in the matching.

The **state-transition equations** become
$$\begin{aligned}
f_{u,1} &= \prod_v (f_{v,0}+f_{v,2})\\
f_{u,2} &= \sum_v (f_{v,1} \cdot \prod_{v', v' \neq v}(f_{v', 0}+f_{v', 2}))\\
f_{u,0} &= \prod_v f_{v,0} + f_{u,2}
\end{aligned}$$

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;
constexpr LL inv(LL x, LL m) { return x > m ? inv(x % m, m) : x > 1 ? inv(m % x, m) * (m - m / x) % m : x; }
constexpr LL mpow(LL a, LL k, LL m) { LL r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }

const int N = 3e5 + 5, Mod = 998244353;
vector<int> G[N];
int n, F[N][3];

void dp(int u, int p) {
    F[u][0] = F[u][1] = 1;
    for (int v : G[u]) if (v != p) {
            dp(v, u);
            F[u][1] = 1LL * F[u][1] * (F[v][0] + F[v][2]) % Mod;
            F[u][0] = 1LL * F[u][0] * F[v][0] % Mod;
        }
    for (int v : G[u]) if (v != p)
            F[u][2] = (F[u][2] + 1LL * F[u][1] * inv(F[v][0] + F[v][2], Mod) % Mod * F[v][1]) % Mod;
    F[u][0] = (F[u][0] + F[u][2]) % Mod;
}

int main() {
    scanf("%d", &n);
    FI(i, 2, n) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dp(1, 0);
    printf("%d\n", F[1][0]);
}
```

KONGROOの基地

このブログを検索

Codeforces 1078C. Vasya and Maximum Matching (Tree+DP)

コメント

コメントを投稿