定向(Orientation)

题目描述

给定一棵树，有 $n$ 个点，$n-1$ 条边。其中第 $i$ 条边，连接 $u_i$ 与 $v_i$。

小爱需要给每一条边分配一个方向，对于 $(u_i,v_i)$，有两种分配方式，或者是指定这条边的方向是从 $u_i$ 到 $v_i$，或者是指定这条边方向从 $v_i$ 到 $u_i$。

给定一个整数 $t$，请统计有多少种分配方案，能够使每条边的方向确定后，恰好有 $t$ 个点没有出边。由于方案数可能比较大，输出对 $998244353$ 取模后的余数。

输入格式

第一行：一个整数 $n$，表示点数

第 $2$ 行到第 $n$ 行：第 $i$ 行有两个整数表示 $u_i$ 与 $v_i$

第 $n+1$ 行：单个整数表示 $t$

输出格式

单个整数，表示可行的方案数对 $998244353$ 取模的余数。

数据范围

• 对于 40% 的数据，$1\leq n \leq 15$；
• 对于 70% 的数据，$1\leq n \leq 100$；
• 对于 100% 的数据，$1\leq n \leq 1000$；

样例输入 #1

4
1 2
3 1
4 3
2

样例输出 #1

4

样例说明 #1

方案1: 2->1,3->1,3->4，此时1,4两点没有出边 方案2: 1->2,1->3,4->3，此时2,3两点没有出边 方案3: 1->2,1->3,3->4，此时2,4两点没有出边 方案4: 1->2,3->1,3->4，此时2,4两点没有出边

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐。

测试点分布