『树上匹配 树形dp』

---

树上匹配

Description

懒惰的温温今天上班也在偷懒。盯着窗外发呆的温温发现，透过窗户正巧能看到一棵 n 个节点的树。一棵 n 个节点的树包含 n-1 条边，且 n 个节点是联通的。树上两点之间的距 离即两点之间的最短路径包含的边数。
突发奇想的温温想要选择一个树上的边集（可以为空）删除， 使得删除后剩下的图的 最大匹配是唯一的。温温想要知道满足条件的边集的数量。满足条件的边集数量可能很多， 请对 998244353 取模。
图的一个匹配是图的一个边子集，满足条件任意两条边都不依附于同一个节点。图的所 有匹配中，边数最多的匹配即为图的最大匹配。

Input Format

第一行一个整数 n。
接下来 n-1 行每行两个整数 ai, bi，表示节点 ai 和 bi 之间存在一条边。
2 ≤ n ≤ 3000 for 40%
2 ≤ n ≤ 300000 for 100%

Output Format

输出一个整数，表示所求的满足条件的边集数量，对 998244353 取模

Sample Input

4 1 2 1 3 1 4

Sample Output

4

解析

先转换题意：最大匹配唯一其实等价于图中的一个点要么孤立，要么属于最大匹配。

这个条件的必要性是显然的，也就是说，最大匹配唯一，该条件一定满足。同样我们也可以证明该条件的充分性：反证法，假设存在一个点，它既不孤立也不属于最大匹配，并且这个图的最大匹配唯一。我们分两种情况讨论：

\(1.\) 这个点连向的点属于最大匹配，那就与最大匹配的唯一性矛盾
\(2.\) 这个点连向的点不属于最大匹配，那就与最大匹配的极大性矛盾

所以这两个命题是等价的。

那么我们就可以考虑树形\(dp\)计数。设\(f1[x]\)代表节点\(x\)等待他的父节点与他匹配，子树\(x\)的方案数，\(f2[x]\)代表节点\(x\)孤立，子树\(x\)的方案数，\(f3[x]\)代表节点\(x\)已经与某一个儿子匹配，子树的\(x\)的方案数。然后列状态转移方程：

\[f1_{x}=\prod_{y\in son(x)}(f2_y+2f3_y)\\f2_x=\prod_{y\in son(x)}(f2_y+f3_y)\\f3_x=\sum_{y\in son(x)} \left ( \frac{\prod_{z\in son(x),z\not= y}(f2_z+2f3_z)}{f2_y+2f3_y}*f1_y \right )\]

为什么\(f3\)都要乘\(2\)，是因为当前节点\(x\)与\(f3\)这种完成状态之间的边可连可不连。关于第三个状态转移方程，其含义为选一个点\(y\)的\(f1\)状态与其匹配，剩下的同理随便选。

\(Code:\)

#include <bits/stdc++.h> using namespace std; const int N = 300020; const long long Mod = 998244353; struct edge { int ver,next; } e[N*2]; int n,t,Head[N]; long long f1[N],f2[N],f3[N]; // f1 means which node is waiting mathcing // f2 means which node is isolated // f3 means which node has already matched inline void insert(int x,int y) {e[++t] = (edge){y,Head[x]} , Head[x] = t;e[++t] = (edge){x,Head[y]} , Head[y] = t; } inline void input(void) {scanf("%d",&n);for ( int i = 1; i < n; i++ ){int x,y;scanf("%d%d",&x,&y);insert( x , y );} } inline long long power(long long a,long long b) {long long res = 1;while ( b ){if ( 1 & b ) res = res * a % Mod;a = a * a % Mod , b >>= 1;}return res; } inline void mul(long long &a,long long b) { a = a * b % Mod; } inline void add(long long &a,long long b) { a += b; if ( a >= Mod ) a -= Mod; } inline void dp(int x,int f) {f1[x] = f2[x] = 1LL;long long val = 1LL;for ( int i = Head[x]; i; i = e[i].next ){int y = e[i].ver;if ( y == f ) continue;dp( y , x );mul( f1[x] , ( f2[y] + 2 * f3[y] ) % Mod );mul( f2[x] , ( f2[y] + f3[y] ) % Mod );mul( val , ( f2[y] + 2 * f3[y] ) % Mod );}for ( int i = Head[x]; i; i = e[i].next ){int y = e[i].ver;if ( y == f ) continue;long long inv = power( f2[y] + 2 * f3[y] , Mod-2 );long long sum = val;mul( sum , inv ) , mul( sum , f1[y] );add( f3[x] , sum );} } int main(void) {input();dp( 1 , 0 );printf("%lld\n", ( f2[1] + f3[1] ) % Mod );return 0; }

---

转载于:https://www.cnblogs.com/Parsnip/p/11203680.html

总结

以上是生活随笔为你收集整理的『树上匹配 树形dp』的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。