树上dp问题

给定一棵n个节点的有根树节点编号范围为1∼n其中根节点编号为1。现在你需要给树上每个节点赋值左括号(或者右括号)问你有多少种赋值方案使得赋值完毕后从根节点到达每一个叶子节点的唯一简单路径所经过的点构成的括号串是一个合法括号串求出方案数对998244353取模的结果我们递归的定义合法括号串空括号串是合法的。若A合法则(A)合法。若A和B合法则AB合法。格式输入格式第一行一个整数T(1≤T≤500)表示测试数据组数对于每组测试数据第一行一个整数n(1≤n≤3000)。接下来n−1n−1行每行两个整数u,v(1≤u,v≤n)表示点uu与点vv之间有一条边。保证单个测试点的所有组测试数据的nn之和不超过3000。输出格式对于每组测试数据输出一行一个整数表示答案。样例 1输入1 4 1 2 2 3 3 4复制输出2复制样例 2输入1 11 1 2 1 3 1 4 2 5 2 8 3 10 5 6 5 7 8 9 10 11复制输出4复制备注对于样例11这是一条链合法的括号串有()()和(())两种答案为2。#include iostream#include vectorusing namespace std;const int MOD 998244353;vectorint adj[3005];long long dp[3005][3005];//来到u节点前欠j个左括号到根后能形成的合法方案数int n;void dfs(int u, int p) {// 1. 先递归处理子节点vectorint children;for (int v : adj[u]) {if (v ! p) {children.push_back(v);dfs(v, u);}}// 2. 计算当前节点在不同初始余额 j 下的方案数// j 是“进入节点 u 之前”的余额for (int j 0; j n; j) {long long ways_as_L 0;long long ways_as_R 0;// 情况 A: 节点 u 填左括号 (// 填完后余额变为 j 1if (j 1 n) {if (children.empty()) {// 如果 u 是叶子填 ( 后余额为 j1// 路径结束要求余额必须为 0所以 j1 0 (不可能)ways_as_L 0;} else {ways_as_L 1;for (int v : children) {ways_as_L (ways_as_L * dp[v][j 1]) % MOD;}}}// 情况 B: 节点 u 填右括号 )// 填完后余额变为 j - 1if (j - 1 0) {if (children.empty()) {// 如果 u 是叶子填 ) 后余额为 j-1// 路径结束要求余额必须为 0即 j 必须是 1ways_as_R (j - 1 0 ? 1 : 0);} else {ways_as_R 1;for (int v : children) {ways_as_R (ways_as_R * dp[v][j - 1]) % MOD;}}}dp[u][j] (ways_as_L ways_as_R) % MOD;}}void solve() {cin n;for (int i 1; i n; i) {adj[i].clear();for (int j 0; j n; j) dp[i][j] 0;}for (int i 0; i n - 1; i) {int u, v;cin u v;adj[u].push_back(v);adj[v].push_back(u);}// 题目要求根节点到叶子的路径。根节点编号为 1。dfs(1, 0);// 最终答案是进入根节点 1 之前余额为 0 的方案数cout dp[1][0] endl;}int main() {ios::sync_with_stdio(false);cin.tie(0);int T;cin T;while (T--) {solve();}return 0;}