{"problem":{"name":"Trees","description":{"content":"ZHY 拥有 $m$ 棵树，每棵树形态相同，且均有 $n$ 个点。定义 $(i,j)$ 是第 $i$ 棵树上的第 $j$ 个点，你需要为每个点 $(i,j)$ 赋一个值 $a_{(i,j)}$，且满足以下条件： - 对于 $\\forall i \\in [1,m],\\forall j \\in [1,n]$，有 $a_{(i,j)}\\in\\{0,1\\}$。 - 对于 $\\forall i \\in ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9161"},"statements":[{"statement_type":"Markdown","content":"ZHY 拥有 $m$ 棵树，每棵树形态相同，且均有 $n$ 个点。定义 $(i,j)$ 是第 $i$ 棵树上的第 $j$ 个点，你需要为每个点 $(i,j)$ 赋一个值 $a_{(i,j)}$，且满足以下条件：\n\n- 对于 $\\forall i \\in [1,m],\\forall j \\in [1,n]$，有 $a_{(i,j)}\\in\\{0,1\\}$。\n\n- 对于 $\\forall i \\in [1,n]$，有 $\\sum_{j=1}^m a_{(j,i)}\\le 1$。\n\n- 对于任意的一条边 $(u,v)$ 和 $i \\in [1,m]$，有 $a_{(i,u)}+a_{(i,v)}\\le 1$。\n\n请你计算有多少种赋值方式，对 $10^9+7$ 取模。注意这 $m$ 棵树是有序的。\n\n## Input\n\n第一行两个正整数 $n,m$。\n\n接下来 $n-1$ 行，每行两个正整数 $u,v$，表示这 $m$ 棵树中每棵树都有一条从 $u$ 到 $v$ 的无向边。保证数据可以构成一棵树。\n\n## Output\n\n输出一行表示答案。\n\n[samples]\n\n## Background\n\nZHY 有很多树，每个树上都有很多点，每个点上都有一个数，但他忘记了每个点上写的数是什么了。\n\n## Note\n\n**本题使用捆绑数据。**\n\n对于所有的数据，$1 \\le n \\le 10^6$，$1 \\le m \\le 10^9$。\n\n- Subtask 0（10 pts）：$n,m \\le 4$。\n- Subtask 1（30 pts）：$n,m \\le 10^3$。\n- Subtask 2（15 pts）：$n \\le 10^3$。\n- Subtask 3（25 pts）：$m=1$。\n- Subtask 4（20 pts）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9161","tags":["动态规划 DP","O2优化","树形 DP"],"sample_group":[["3 1\n1 2\n2 3","5"],["5 2\n1 2\n1 3\n2 4\n2 5","103"]],"created_at":"2026-03-03 11:09:25"}}