博客

题目大意

给定一张



n

(

3

≤

n

≤

1

0

5

)

n(3\le n \le 10^5)






n


(


3




≤








n




≤








1



0










5









)





个节点的树(



n

n






n





为奇数),将这



n

−

1

n-1






n




−








1





条边两两分组,

要求:

分到同一组的边有相同的顶点。

求一共有多少种方法。结果对



998244353

998244353






9


9


8


2


4


4


3


5


3





取模

原题地址

思路

假设第一个节点是父节点。

可以发现以下规律:

• 对于一个节点
  
  
  
  u

  u
  
  
  
  
  
  
  u
  
  
  
  
  
  的子节点
  
  
  
  v

  v
  
  
  
  
  
  
  v
  
  
  
  
  
  ,如果
  
  
  
  v

  v
  
  
  
  
  
  
  v
  
  
  
  
  
  的“可供使用”的边数(除去与
  
  
  
  u

  u
  
  
  
  
  
  
  u
  
  
  
  
  
  相连的)为偶数,那么与
  
  
  
  u

  u
  
  
  
  
  
  
  u
  
  
  
  
  
  相连的这条边对于
  
  
  
  u

  u
  
  
  
  
  
  
  u
  
  
  
  
  
  来说,就是“可供使用”的了。(“可供使用”的意思就是可以与这个节点上的其它节点结合)。

• 对于一个节点
  
  
  
  u

  u
  
  
  
  
  
  
  u
  
  
  
  
  
  的子节点
  
  
  
  v

  v
  
  
  
  
  
  
  v
  
  
  
  
  
  ,如果
  
  
  
  v

  v
  
  
  
  
  
  
  v
  
  
  
  
  
  的“可供使用”的边数(除去与
  
  
  
  u

  u
  
  
  
  
  
  
  u
  
  
  
  
  
  相连的)为奇数,那么与
  
  
  
  u

  u
  
  
  
  
  
  
  u
  
  
  
  
  
  相连的这条边就要用来与
  
  
  
  v

  v
  
  
  
  
  
  
  v
  
  
  
  
  
  相连的边组合,否则就无法成功分配。

那么对于每个节点可供使用的边,如果是偶数,那我们就两两分组,如果是奇数,那么我们留下与父节点相连的边,剩下的两两分组。

那么



n

n






n





(



n

n






n





为偶数)个数两两分组的计算方式:

C

n

2

∗

C

n

−

2

2

∗

.

.

.

∗

C

2

2

A

n

/

2

n

/

2

\frac{C_n^2 * C_{n-2}^2 * …*C_2^2}{A_{n/2}^{n/2}}


















A











n


/


2










n


/


2






​

























C










n








2





​














∗





C











n


−


2









2





​














∗




.


.


.




∗





C










2








2





​















​



















经过一番

高强度

化简之后得:





(

n

−

1

)

∗

(

n

−

3

)

∗

.

.

.

3

∗

1

(n-1) * (n – 3) * … 3 * 1






(


n




−








1


)




∗








(


n




−








3


)




∗








.


.


.


3




∗








1

那么剩下就是解决

可供使用

的边的问题了,该如何计算呢？

这个“可供使用”的边是一个“递归”定义的,我们只看一个点和它的边,是没有办法看出来它那些边是可以使用的,必须看它的子节点的可以使用的边，而它的子节点又和子节点的子节点有关系…

所以我们就用类似

树形DP

的方法,从根节点开始dfs:

那么边界条件:

叶子节点没有可供使用的边,所以也算偶数,那么它和父节点相连的这条边,就可以被父亲节点使用。

那么剩下的就一直按照最开始分析的计算即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const long long Mod = 998244353;
const int maxN = 1e5 + 7;

int n, d[maxN];
vector<int> e[maxN];
long long f[maxN];

bool dfs(int x, int fa)
{
    int cnt = 0;
    f[x] = 1;
    for(int i = 0; i < e[x].size(); ++i) {
        int y = e[x][i];
        if(y == fa)
            continue;
        if(!dfs(y, x))
            cnt++;
        f[x] = f[x] * f[y] % Mod;    
    }
    for(int i = 1; i <= cnt; i +=2)
        f[x] = f[x] * i % Mod;
    return cnt & 1;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    printf("%lld\n", f[1]);
    return 0;
}