「MCOI-08」Photoelectric Effect

Luogu

IDLGP8280

Time1000ms

Memory256MB

DifficultyP5

洛谷原创O2优化树形 DP洛谷月赛状压 DP

有一棵 $n$（$1\le n\le 10^5$）个点的树以及 $k$（$2\le k\le 5$）个颜色，根节点为 $1$。同时，给定一个颜色合并函数 $a\otimes b$，满足当 $1\le a,b\le k$，有 $1\le a\otimes b\le k$。请问有多少个方案对所有点染色，使得当点对 $u,v$ 之间没有祖先关系，有： - $u$ 和 $v$ 最近公共祖先的颜色为点 $u$ 的颜色和点 $v$ 的颜色之并。答案对 $10^9+7$ 取模。 ## Input 本题有多组数据，第一行一个正整数 $t$（$1\le t\le 10^3$），为数据组数。接下来 $t$ 组数据，其中对于每一组数据：第一行两个正整数 $n,k$。接下来 $k$ 行，每行 $k$ 个正整数。第 $i$ 行第 $j$ 个数为 $i\otimes j$ 的值。接下来 $n-1$ 个正整数 $f_2,f_3,\dots,f_n$，其中 $f_i$ 是 $i$ 的父亲节点。 ## Output 对于每一组数据：输出一个整数，表示答案。 [samples] ## Note #### 样例 1 解释树的形态如下： ![](https://cdn.luogu.com.cn/upload/image_hosting/twht22a6.png) 设 $w_i$ 为第 $i$ 个点的点权，则有如下 $4$ 种分配方式： - $w_i=\{1,1,1,1,1\}$； - $w_i=\{2,2,2,1,1\}$； - $w_i=\{2,1,1,2,2\}$； - $w_i=\{1,2,2,2,2\}$。 #### 数据规模与约定 **本题采用捆绑测试。** 对于 $100\%$ 的数据，$1\le n,\sum n\le10^5$，$2\le k\le 5$，$1\le f_i<i$。对于 $100\%$ 的数据，$1\le t\le 1000$。 - Subtask 1（5 pts）：$n\le5$； - Subtask 2（11 pts）：树上任何节点孩子个数至多为 $2$； - Subtask 3（23 pts）：树上任何节点孩子个数至多为 $3$； - Subtask 4（13 pts）：$k=2$； - Subtask 5（17 pts）：$k\le3$； - Subtask 6（31 pts）：无特殊限制。

Samples

Input #1

Output #1

4
2

API Response (JSON)

{
  "problem": {
    "name": "「MCOI-08」Photoelectric Effect",
    "description": {
      "content": "有一棵 $n$（$1\\le n\\le 10^5$）个点的树以及 $k$（$2\\le k\\le 5$）个颜色，根节点为 $1$。同时，给定一个颜色合并函数 $a\\otimes b$，满足当 $1\\le a,b\\le k$，有 $1\\le a\\otimes b\\le k$。 请问有多少个方案对所有点染色，使得当点对 $u,v$ 之间没有祖先关系，有：  - $u$ 和 $v$ 最近公共祖先的颜色为",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8280"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一棵 $n$（$1\\le n\\le 10^5$）个点的树以及 $k$（$2\\le k\\le 5$）个颜色，根节点为 $1$。同时，给定一个颜色合并函数 $a\\otimes b$，满足当 $1\\le a,b\\le k$，有 $1\\le a\\otimes b\\le k$。\n\n请问有多少个方案对所有点染色，使得当点对 $u,v$ 之间没有祖先关系，有：\n\n - $u$ 和 $v$ 最近公共祖先的颜色为...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments