#P6021. 「from CommonAnts」寻找 LCR

「from CommonAnts」寻找 LCR

题目描述

没有常人知道她在哪里——LCR 的神秘只有真正的神犇才能看到。
幸运的是,某附中确实存在一个这样的神犇。一天,神犇发现了一件事情:LCR 从自己的视野中消失了。
显然,这不可能是因为神犇变弱而失去了 LCR 的青睐,而是 LCR 离开了这座城市的缘故。
神犇踏上了寻找 LCR 的征程。
神犇走过了千山万水,一天,他遇到了 LCR 的兄长——LCT。LCT 告诉他,他的身上沾染了过多的蒟蒻气息,因此看不到 LCR。LCT 还告诉他,他需要到东海找龙王消除自己身上的蒟蒻气息。
神犇知道,普通的蒟蒻是不可能在他这样的神犇身上留下蒟蒻气息的,只有像 LCA 这样的蒟蒻才会在他的身上留下蒟蒻气息。
神犇决定超时空传送去东海。神犇现在要传送到一个有 nn 个传送点的网络中,传送网络中有 mm 条路,但神犇发现每条路上都有至少一个像 LCA 那样的蒟蒻。神犇知道,自己如果沾染了过多的蒟蒻气息,就会即使到了东海也无法消除了。根据蒟蒻学第二定律,蒟蒻气息只会从蒟蒻多的地方向蒟蒻少的地方传递,因此神犇在穿过一条路后,他身上的蒟蒻气息会变成穿过之前的值和这条路径上的蒟蒻数量的最大值。神犇还发现,在不同的时间,他的家乡和东海对应的传送网络的传送点是不同的。神犇想知道,如果他知道自己应该从哪里进入排序网络和从何处离开,他至少要沾染多少蒟蒻气息。由于传送网络中的蒟蒻气息太过浓郁,你可以认为神犇在进入时身上没有蒟蒻气息。保证传送网络中任意两点相互可达,且道路是双向的。一条道路连接的必定是两个不同的传送点,但一对传送点之间可能有两条道路。

给你一个 nn 个点 mm 条边的无向连通图,编号为 11nn ,没有自环,可能有重边,每一条边有一个正权值 ww 。给出 qq 个询问,每次给出两个不同的点 uuvv ,求一条从 uuvv 的路径上边权的最大值最小是多少。

输入格式

输入第一行两个整数 nnmm

接下来 mm 行,每行三个整数 ai,bi,wia_i,b_i,w_iaibia_i\neq b_i),表示一条连接传送点 aia_ibib_i 的道路,上面的蒟蒻数量为 wiw_i

接下来一行一个整数 qq,表示询问数量。

接下来一行四个整数 A,B,C,PA,B,C,P,表示询问的生成方式。

由于本题数据规模极大,直接输入输出会占用比计算多数倍的时间,因此对询问的输入输出进行了压缩。

输入压缩方法是:读入四个整数 A,B,C,PA,B,C,P,每次询问调用以下函数生成 uuvv

int A, B, C, P;

int rnd() {
    return A = (A * B + C) % P;
}

每次询问时的调用方法为:

u = rnd() % n + 1, v = rnd() % n + 1;

uuvv 相等则答案为 00

数据保证 0A<P,0C<P,P(B+1)<23110\leq A<P,0\leq C<P,P(B+1)<2^{31}-1

输出格式

输出共一行一个整数,表示所有询问的答案之和模 10000000071000000007 的值。

由于本题数据规模极大,直接输入输出会占用比计算多数倍的时间,因此对询问的输入输出进行了压缩。

输出压缩方法是:输出所有询问的答案之和模 10000000071000000007 的值。

5 7
1 2 8
2 3 9
3 1 2
3 4 7
1 4 4
3 5 6
1 4 9
10
233 17 66666 19260817
32

数据范围与提示

测试点编号 nn mm qq ww 备注
11 100100 9999 100100 1wi1031\le w_i\le 10^3 ai=bi1a_i=b_i-1
22
33 200200
44 20002000 19991999 20002000 ai=bi1a_i=b_i-1
55
66 50005000
77 1000010000 99999999 200000200000
88 3000030000
99 3000030000 2999929999 ai=bi1a_i=b_i-1
1010 5000050000
1111 4000040000 3999939999 500000500000 1wi109+71\le w_i\le 10^9+7
1212 8000080000
1313 7000070000 6999969999
1414 100000100000
1515 6999969999 50000005000000 ai=bi1a_i=b_i-1
1616 70000007000000
1717 1000000010000000
1818 100000100000 50000005000000
1919 70000007000000
2020 1000000010000000

对于 100%100\% 的数据,n70000n\leq 70000m100000m\leq 100000q107q\leq 10^7