定向(Orientations)

题目描述

给定一棵树，有 $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$ 取模的余数。

样例输入 #1

4
1 2
3 1
4 3
2

样例输出 #1

4

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP 7级（树形动态规划、图论），难度等级：⭐⭐⭐⭐。

测试点分布