#1918. 神奇的子图

    ID: 1918 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1972来源:qoj.ac数据:公开样例枚举

神奇的子图

神奇的子图

题目描述

标题: 神奇的子图 - Problem - QOJ.ac

#10353. 神奇的子图

Statistics

The problem was used in the following contests:

xxx 很喜欢图论问题。最近,xxx 的好朋友 y0rkllu 和 y0rklld 送给 xxx 一份礼物——一张无自环、无重边的无向图 G=(V,E),其中 n=|V|,m=|E|。有趣的是,任取 V 中的 7 个点构成集合 V′,都存在三个不同的点 p,q∈V′,x∈V−{p,q},使得从图中删去点 x 后, p 和 q 不连通。

如果一张图 G=(VG,EG) 满足这张图连通,且对于任意的节点 p∈VG,都有 degG⁡(p)≤k,则 xxx 称图 G 是 k-神奇的。例如,任意一个单点都是 0-神奇的,任意一个链或环都是 2-神奇的。xxx 认为所有的 k-神奇的图都是很漂亮的。

现在 xxx 想要取图 G 的一个 k-神奇的子图 G′=(V′,E′),V′⊆V,E′⊆E,作为房子的装饰品。在图中,xxx 对每个节点都有一个美观评分 vp——xxx 自然希望这张子图中,所有点的美观评分的和最大。并且 xxx 讨厌重复,他希望每天的装饰都能不同。因此 xxx 希望你帮他求出图 G 的所有 k-神奇子图中,美观评分和最大的那个子图的美观评分和是多少,以及有多少不同的 k-神奇子图的美观评分和达到最大值。对于后一个问题,xxx 只需要知道不同的子图个数除以 64123 的余数即可。两张子图 G1=(V1,E1),G2=(V2,E2) 不同,当且仅当 V1≠V2 或 E1≠E2。

随着时间的变动,xxx 可能会修改某些节点的美观评分——比如某个节点看腻了,或想念某个节点了。因此,你还需要帮助他在每次美观评分发生变化的时候,都求出上述两个问题的答案。

输入格式

第一行包含 3 个整数 n,m,k,表示 xxx 的简单图 G 的边数、点数及 xxx 喜欢的 k-神奇子图的 k 值;

第二行包含 n 个整数 v1,v2,…,vn,表示每个节点初始情况下的美观评分;

接下来 m 行,其中第 i 行包含 2 个整数 xi,yi∈[1,n] ,表示图中的第 i 条双向边连接节点 xi 和节点 yi;

接下来一行包含 1 个整数 q,表示 xxx 修改美观评分的次数;

接下来 q 行,其中第 i 行包含两个整数 pi,wi,表示 xxx 在第 i 次修改中,将节点 pi 的美观评分修改为了 wi。

输出格式

在刚开始及每次修改过后输出 1 行答案,因此总共应该输出 q+1 行;输出的每一行包含两个数,分别表示“美观评分和最大的那个子图的美观程度是多少”和“有多少不同的 k-神奇子图的美观评分和达到最大值(除以 64123 的余数)”这两个问题的答案。

样例输入

5 5 2
1 2 1 2 2
2 3
2 1
1 4
1 3
1 5
1
2 1

样例输出

6 4
5 5

样例说明

在最开始,存在以下 4 种美观评分之和为最大值 6 的方案:

编号 V′ E′ 1 {1,2,3,4} {(2,3),(1,2),(1,4)} 2 {1,2,3,4} {(2,3),(1,3),(1,4)} 3 {1,2,3,5} {(2,3),(1,2),(1,5)} 4 {1,2,3,5} {(2,3),(1,3),(1,5)}

当 xxx 修改节点 2 的美观程度为 1 后,存在以下 5 种美观评分之和为最大值 5 的方案:

编号 V′ E′ 1 {1,2,3,4} {(2,3),(1,2),(1,4)} 2 {1,2,3,4} {(2,3),(1,3),(1,4)} 3 {1,2,3,5} {(2,3),(1,2),(1,5)} 4 {1,2,3,5} {(2,3),(1,3),(1,5)} 5 {1,4,5} {(1,4),(1,5)}

数据范围与约定

对于所有数据,保证 n≥2,m,q≥0,2≤k≤3,1≤vi,wi≤5000。

每个测试点的详细信息如下表:

子任务 总分值 测试点 n m k q 特殊性质 1 7 1 ≤10 ≤20 =3 ≤100 无 2 18 2,3 ≤10000 =n−1 =2 ≤1000 1 3 7 4,5 ≤50000 =n−1 =2 ≤50000 1 4 15 6,7,8 ≤100000 =n−1 =2 ≤200000 1 5 12 9,10 ≤100 ≤300 =2 =0 2,3 6 9 11,12 ≤1000 ≤3000 =3 =0 3 7 5 13 ≤30000 ≤100000 =3 =0 无 8 14 14,15 ≤100000 ≤300000 =3 =0 无 9 3 16 ≤30000 ≤55000 =3 ≤10000 无 10 10 17~20 ≤30000 ≤100000 =3 ≤10000 无

特殊性质 1:保证 G 是一棵 n 个节点的无根树。

特殊性质 2:保证所有的 vi,wi 均为 1。

特殊性质 3:任取 V 中的 5 个点构成集合 V′,都存在三个不同的点 p,q∈V′,x∈V−{p,q},使得从图中删去点 x 后, p 和 q 不连通。

对于每个测试点,如果你每行的第一个数都是对的,但某些行的第二个数出错了,你仍然可以获得该测试点 60% 的分数。(如果你不打算回答第二个问题,请随意输出第二个数)

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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