Trees

Luogu

IDLGP9161

Time2000ms

Memory128MB

DifficultyP4

动态规划 DPO2优化树形 DP

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 [1,n]$，有 $\sum_{j=1}^m a_{(j,i)}\le 1$。 - 对于任意的一条边 $(u,v)$ 和 $i \in [1,m]$，有 $a_{(i,u)}+a_{(i,v)}\le 1$。请你计算有多少种赋值方式，对 $10^9+7$ 取模。注意这 $m$ 棵树是有序的。 ## Input 第一行两个正整数 $n,m$。接下来 $n-1$ 行，每行两个正整数 $u,v$，表示这 $m$ 棵树中每棵树都有一条从 $u$ 到 $v$ 的无向边。保证数据可以构成一棵树。 ## Output 输出一行表示答案。 [samples] ## Background ZHY 有很多树，每个树上都有很多点，每个点上都有一个数，但他忘记了每个点上写的数是什么了。 ## Note **本题使用捆绑数据。** 对于所有的数据，$1 \le n \le 10^6$，$1 \le m \le 10^9$。 - Subtask 0（10 pts）：$n,m \le 4$。 - Subtask 1（30 pts）：$n,m \le 10^3$。 - Subtask 2（15 pts）：$n \le 10^3$。 - Subtask 3（25 pts）：$m=1$。 - Subtask 4（20 pts）：无特殊限制。

Samples

Input #1

3 1
1 2
2 3

Output #1

Input #2

Output #2

API Response (JSON)

{
  "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments