U490735 习惯孤独

## 【题目背景】 "私を置いてゆかないで，ひとりが好きなわけじゃないのよ" 但分别总会到来\...\... ## 【题目描述】 给你一棵树，你要去切这个树！ 具体来说，最开始你有一棵树 $T_0$。 每次可以选择一条边 $(x,y)$ 把这条边切断，然后选择剩下的两个连通块 $T_{i,1},T_{i,2}$ 其中一个，递归到子问题，即 $T_{i+1}\gets T_{i,k}$。 你可以任意切 $k\le 6$ 次这棵树，但额外的，你希望每次切完树的大小是确定的，具体来说，给定 $k$ 个正整数 $a_1,a_2,\cdots ,a_k$ 你需要保证每次切树后，$|T_i|=a_i$。 请你计算有多少种本质不同的切树方法。答案对 $998244353$ 取模。 我们记 $A=\{T_0,T_1,\cdots T_k\}$ 表示每次切完剩下的树的集合，那么两种切树方案不同当且仅当，他们对应的 $A$ 集合不同。 ## 【输入格式】 从文件 ***lone.in*** 中读入数据。 第一行一个正整数 $n$ 表示初始树的点数。 接下来 $n-1$ 行每行两个整数 $(u,v)$ 描述一条树边。 接下来一行一个整数 $k$，含义同题目描述。 接下来一行 $k$ 个整数分别表示 $a_1,a_2,\cdots a_k$，含义同题目描述。 ## 【输出格式】 输出到文件 ***lone.out*** 中。 输出一行一个整数，表示合法切树的方案。 ## 【样例 1 输入】 3 2 3 1 2 2 2 1 ## 【样例 1 输出】 4 ## 【样例 2】 见选手目录下的 ***lone/lone2.in*** 与 ***lone/lone2.out***。 ## 【样例 3】 见选手目录下的 ***lone/lone3.in*** 与 ***lone/lone3.out***。 ## 【数据范围】 对于所有测试数据，保证 $2\le n\le 5000,k\le \min(n-1,6)$，$a_1>a_2>\cdots >a_k$。 | 测试点编号 | $n\le$ | $k\le$ | | ------------ | ------ | ------ | | $1\sim3$ | $5$ | $5$ | | $4$ | $100$ | $2$ | | $5 \sim 6$ | $100$ | $3$ | | $7 \sim 8$ | $5000$ | $2$ | | $9 \sim 11$ | $5000$ | $3$ | | $12\sim 15$ | $5000$ | $4$ | | $16 \sim 20$ | $5000$ | $6$ |

无

无

无