#P5409. [2018年湖南省队集训]墨水大师

    ID: 4421 传统题 2000ms 512MiB 尝试: 103 已通过: 27 难度: 8 上传者: 标签>CF2400提高+/省选-仙人掌图顶点着色深度优先搜索乘法原理递推计数固定底数幂分块预处理快速幂模逆元

[2018年湖南省队集训]墨水大师

题目描述

给定一棵仙人掌。每次询问给定颜色数 CC,求给每个顶点染上 CC 种颜色之一、使每条边的两端颜色不同的方案数。

输入格式

第一行三个正整数 N,M,QN,M,Q,分别表示顶点数、边数和询问数。

接下来 MM 行,每行两个正整数 x,yx,y,表示连接顶点 x,yx,y 的一条边。

接下来 QQ 行,每行一个正整数 CC,表示本次询问的颜色数。

输出格式

输出 QQ 行,每行一个非负整数,表示对应询问的方案数模 998244353998244353 的结果。

样例

3 3 3
1 2
1 3
2 3
2
3
4
0
6
24

数据范围

  • 对于 10%10\% 的数据,N,Q,C≤5N,Q,C\le5。
  • 对于 30%30\% 的数据,N,Q,C≤15N,Q,C\le15。
  • 对于 50%50\% 的数据,N,Q≤2000N,Q\le2000。
  • 对于另外 10%10\% 的数据,M=N−1M=N-1。
  • 对于所有数据,N,Q≤100000N,Q\le100000,M≤2N−2M\le2N-2,C≤109C\le10^9。保证输入为合法仙人掌,无重边和自环。

原 PDF 题面