#1918. 神奇的子图
神奇的子图
神奇的子图
题目描述
标题: 神奇的子图 - Problem - QOJ.ac
#10353. 神奇的子图
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