虚人「无」

Luogu

IDLGP9208

Time1000ms

Memory128MB

DifficultyP4

树形数据结构前缀和传智杯

给定二元序列 $\{(v_i,c_i)\}$ 和一棵以 $1$ 为根的有根树。第 $i$ 个点的点权是 $(v_i,c_i)$。 - 定义一个非根节点的权值为其子树内的 $c$ 的积乘上其子树补的 $v$ 的积。 - 定义一个根节点的权值为其子树内的 $c$ 的积。形式化的讲，若 $u$ 不为根节点，则 $u$ 的权值 $f_u$ 为： $$f_u=\prod\limits_{v\in \operatorname{substree}(u)} c_v\times \prod\limits_{v\notin \operatorname{substree}(u)} v_v$$ 否则，其权值 $f_u$ 为： $$f_u=\prod\limits_{v=1}^n c_v$$ 试求整棵树**所有节点的权值之和**，答案对 $m$ 取模。请注意：**保证 $\bm m$ 是质数**。 ## Input 第一行两个正整数 $n,m$。接下来 $n-1$ 行，每行两个数 $u,v$，表示 $u,v$ 之间有一条边。接下来一行 $n$ 个数，表示 $c_{1, 2, \dots, n}$。接下来一行 $n$ 个数，表示 $v_{1, 2, \dots, n}$。 ## Output 输出一个数，表示答案对 $m$ 取模后的结果。 [samples] ## Background 一点也不美丽的不死鸟。那双锐爪，沾染了无辜的鲜血。 ## Note ### 样例解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/olehwn2w.png) （图片有误，应该交换 $v,c$ 的权值。） ### 数据范围及约定对于 $100\%$ 的数据，满足 $1\le n\leq 3\times 10^5$，$1\leq v_i,c_i,m\leq 10^9$。

Samples

Input #1

3 998244853
1 2
1 3
2 1 2
1 2 2

Output #1

Input #2

5 998244353
1 2
1 3
1 4
4 5
5 5 5 2 3
6 6 1 5 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "虚人「无」",
    "description": {
      "content": "给定二元序列 $\\{(v_i,c_i)\\}$ 和一棵以 $1$ 为根的有根树。第 $i$ 个点的点权是 $(v_i,c_i)$。 - 定义一个非根节点的权值为其子树内的 $c$ 的积乘上其子树补的 $v$ 的积。 - 定义一个根节点的权值为其子树内的 $c$ 的积。 形式化的讲，若 $u$ 不为根节点，则 $u$ 的权值 $f_u$ 为： $$f_u=\\prod\\limits_{v\\in \\",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9208"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定二元序列 $\\{(v_i,c_i)\\}$ 和一棵以 $1$ 为根的有根树。第 $i$ 个点的点权是 $(v_i,c_i)$。\n\n- 定义一个非根节点的权值为其子树内的 $c$ 的积乘上其子树补的 $v$ 的积。\n- 定义一个根节点的权值为其子树内的 $c$ 的积。\n\n形式化的讲，若 $u$ 不为根节点，则 $u$ 的权值 $f_u$ 为：\n\n$$f_u=\\prod\\limits_{v\\in \\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments