[COCI 2021/2022 #4] Šarenlist

Luogu

IDLGP8315

Time1000ms

Memory512MB

DifficultyP5

并查集2021状态合并容斥原理COCI（克罗地亚）

Vito 和 Karlo 被这些彩色的树迷住了，他们同时也注意到了一些事物。他们正在看的每棵树都可以看做是一个树图，即任意两点之间仅存在一条路径的无向图。他们正在看的每棵树都有这样的特点：每条边上的颜色都是 $k$ 种颜色中的一种。如果树上的一个路径是彩色的，意味着这条路径上至少包含两种不同颜色的边。早上树的魔力全部消失了。Vito 和 Karlo 还记得 $m$ 条彩色路径的起点和终点。他们想知道：满足条件的树的有多少种可能？由于答案可能很大，所以请将答案对 $10^9+7$ 取模。 ## Input 第一行包含三个整数 $n,m,k$，分别表示树上的节点数、Vito 和 Karlo 所记得的彩色路径的个数和树枝的颜色总数。接下来 $n-1$ 行，第 $i+1$ 行包含两个整数 $a_i,b_i$，表示点 $a_i$ 和点 $b_i$ 之间有一条树边。接下来 $m$ 行，第 $n+j$ 行包含两个整数 $c_j,d_j$，表示从点 $c_j$ 到点 $d_j$ 之间有一条彩色路径。保证 $c_j$ 和 $d_j$ **不相邻**。 ## Output 仅一行，输出满足条件的树的可能数，答案需对 $10^9+7$ 取模。 [samples] ## Background 温暖的夏夜，Vito 和他的好朋友 Karlo 躺在森林的空地上看星星。突然，Vito 大喊：“Karlo，你看！我们周围的树都在变色！”“哇，真是五彩缤纷！”Karlo 惊讶地说。的确，森林中的树枝开始变色。 ## Note **【样例 1 解释】** 第一种情况是点 $1$ 和点 $2$ 之间的边涂颜色 $1$，点 $2$ 和点 $3$ 之间的边涂颜色 $2$。第二种情况是点 $1$ 和点 $2$ 之间的边涂颜色 $2$，点 $2$ 和点 $3$ 之间的边涂颜色 $1$。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - Subtask 1（10 pts）：$m = 1$。 - Subtask 2（15 pts）：$m = 2$。 - Subtask 3（10 pts）：每个树边最多属于 $m$ 条彩色路径中的一条。 - Subtask 4（10 pts）：$1 ≤ n ≤ 15, k = 2$。 - Subtask 5（65 pts）：没有额外限制。对于 $100\%$ 的数据，$3 ≤ n ≤ 60, 1 ≤ m ≤ 15, 2 ≤ k ≤ 10^9, 1 ≤ a_i,b_i, c_j , d_j ≤ n$。 **【提示与说明】** **本题分值按 COCI 原题设置，满分 $110$。** **题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T5 Šarenlist。**

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2021/2022 #4] Šarenlist",
    "description": {
      "content": "Vito 和 Karlo 被这些彩色的树迷住了，他们同时也注意到了一些事物。他们正在看的每棵树都可以看做是一个树图，即任意两点之间仅存在一条路径的无向图。他们正在看的每棵树都有这样的特点：每条边上的颜色都是 $k$ 种颜色中的一种。如果树上的一个路径是彩色的，意味着这条路径上至少包含两种不同颜色的边。 早上树的魔力全部消失了。Vito 和 Karlo 还记得 $m$ 条彩色路径的起点和终点。他们",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8315"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vito 和 Karlo 被这些彩色的树迷住了，他们同时也注意到了一些事物。他们正在看的每棵树都可以看做是一个树图，即任意两点之间仅存在一条路径的无向图。他们正在看的每棵树都有这样的特点：每条边上的颜色都是 $k$ 种颜色中的一种。如果树上的一个路径是彩色的，意味着这条路径上至少包含两种不同颜色的边。\n\n早上树的魔力全部消失了。Vito 和 Karlo 还记得 $m$ 条彩色路径的起点和终点。他们...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments