P5206 [WC2019] 数树

    • 103通过
    • 289提交
  • 题目提供者 Anguei 管理员
  • 评测方式 云端评测
  • 标签 WC/CTSC/集训队 2019
  • 难度 NOI/NOI+/CTSC
  • 时空限制 4000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    白兔喜欢树。

    白云喜欢数数。

    有 $n$ 只鼠,白兔用 $n - 1$ 根蓝色绳子把它们连成了一棵树,每根蓝色绳子连着两只鼠,白云用 $n - 1$ 根红色绳子把它们连成了一棵树,每根红色绳子连接着两只鼠。

    白云要给予每只鼠一个数。这个数可以是 $[1, y]$ 中的任意一个整数。

    白兔给了白云一个要求:对于两只鼠 $p, q$,若存在一条连接这两只鼠的路径同时属于这两棵树,则 $p$ 和 $q$ 必须被给予相同的整数。存在一条路径同时属于这两棵树指的是:存在一个序列 $(a_1 = p, a_2, \cdots , a_m = q)$,使得:对于所有 $i \in [1, m - 1]$,都有 $a_i$ 和 $a_{i+1}$ 既有一根红色绳子直接相连也有一根蓝色绳子直接相连。

    白云想知道,她有多少种给予数的方案呢?

    鼠在不停地挣扎,想要摆脱绳子的束缚。白云还没有思考出来,鼠便把红色绳子都咬断了。

    白兔有些气恼,但是他还是想要知道答案。他便问白云:对于所有红色绳子的连接方案,答案的总和(即求所有红色绳子连接方案的给予数方案之和)是多少?

    鼠在不停地挣扎,想要摆脱绳子的束缚。白云还没有思考出来,鼠便把蓝色绳子也咬断了。

    白兔有些气恼,但是他还是想要知道答案。他便问白云:对于所有红色和蓝色绳子的连接方案,答案的总和(即求所有红色和蓝色绳子连接方案的给予数方案之和)是多少?两个方案不同当且仅当存在至少一对鼠,在两种方案中,这两只鼠之间直接连接的绳子不同(两只鼠之间连接绳子的可能性有 4 种:没有绳子直接连接,只有红色绳子直接连接,只有蓝色绳子直接连接,两种颜色的绳子均直接连接)。

    白云哭了。

    题目描述

    本题包含三个问题:

    • 问题 0:已知两棵 $n$ 个节点的树的形态(两棵树的节点标号均为 $1$ 至 $n$),其中第一棵树是红树,第二棵树是蓝树。要给予每个节点一个 $[1, y]$ 中的整数,使得对于任意两个节点 $p, q$,如果存在一条路径 $(a_1 = p, a_2, \cdots , a_m = q)$ 同时属于这两棵树,则 $p, q$ 必须被给予相同的数。求给予数的方案数。
      • 存在一条路径同时属于这两棵树的定义见「题目背景」。
    • 问题 1:已知蓝树,对于红树的所有 $n^{n-2}$ 种选择方案,求问题 0 的答案之和。
    • 问题 2:对于蓝树的所有 $n^{n-2}$ 种选择方案,求问题 1 的答案之和。

    提示:$n$ 个节点的树一共有 $n^{n-2}$ 种。

    在不同的测试点中,你将可能需要回答不同的问题。我们将用 $\text{op}$ 来指代你需要回答的问题编号(对应上述 0、 1、 2)。

    由于答案可能很大,因此你只需要输出答案对 $998, 244, 353$ 取模的结果即可。

    输入输出格式

    输入格式:

    第一行三个用空格隔开的整数 $n, y, \text{op}$。 如果 $\text{op} = 0$,则接下来 $2 \times (n - 1)$ 行,前 $(n - 1)$ 行每描述一条蓝色绳子,接下来 $(n - 1)$ 行每行描述一条红色绳子。
    如果 $\text{op} = 1$,则接下来 $(n - 1)$ 行,每行描述一条蓝色绳子。
    如果 $\text{op} = 2$,则接下来没有输入。
    描述绳子的各行将包含两个用空格隔开的整数,分别表示被这条绳子连接的两只鼠的编号。鼠的编号是从 $1$ 开始的。

    输出格式:

    输出一个整数,表示答案对 $998, 244, 353$ 取模的结果。

    输入输出样例

    输入样例#1: 复制
    3 2 0
    1 2
    2 3
    1 2
    2 3
    输出样例#1: 复制
    2
    
    输入样例#2: 复制
    3 2 1
    1 2
    2 3
    输出样例#2: 复制
    10
    输入样例#3: 复制
    3 2 2
    
    输出样例#3: 复制
    30
    

    说明

    样例说明 1

    两棵树相同,所以任意两个点都必须被给予相同的数,方案数为 $2$。

    样例说明 2

    红树共有三种可能的情况:

    1. 包含绳子 $(1, 2)$(表示连接 $1, 2$ 号鼠的绳子,下同)、$(2, 3)$:此时任意两只鼠都必须被给予相同的数,问题 0 的答案为 $2$。
    2. 包含绳子 $(1, 2)$、$(1, 3)$:此时 $1$ 号鼠和 $2$ 号鼠必须被给予相同的数,问题 0 的答案为 $2 \times 2 = 4$。
    3. 包含绳子 $(2, 3)$、$(1, 3)$:此时 $2$ 号点和 $3$ 号点必须被给予相同的数,问题 0 的答案为 $2 \times 2 = 4$。

    综上,问题 1 的答案为 $2 + 4 + 4 = 10$。

    样例说明 3

    蓝树一共有三种可能的情况。不难发现,对于蓝树的每一种情况,求得的问题 1 的答案都是 $10$。所以答案为 $10 \times 3 = 30$。

    洛谷按照集训队分值赋分

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。