有一张n个点m条边的无向连通图G，每条边有长度ci，有一个人在上面走 有q组询问，每组询问给出si,ti,ri，表示问你是否存在一条从si出发到ti结束长度为ri%Mod的路径 注意这里的路径长度是∑ci*2^i n,m,q<=50000,Mod<=1000000且Mod为奇数
考虑把这个过程倒过来，这样每走一次就会变成 2 x + w 2x + w 2x+w。
朴素做法是判断到某个点，值为 x x x 是否可行，考虑寻找一些性质来优化这个做法。
不难发现直接做的话是单向边，这样处理起来比较困难。
考虑一条边 ( u , v , w ) (u, v, w) (u,v,w)，如果在这条边上进行左右横跳的话，可以从 ( u , x ) (u, x) (u,x) 转移到 ( v , 2 x + w ) (v, 2x + w) (v,2x+w)，即一个状态有唯一后继。同时因为模数为奇数，这一过程是可逆的，所以一个状态有唯一前驱。因此这会形成一个环。我们不断在这个环上走，可以从 ( v , 2 x + w ) (v, 2x + w) (v,2x+w) 走到 ( u , x ) (u, x) (u,x)。因此可达性是双向的。
考虑一个点的某两条出边 ( a , b , w 1 ) , ( a , c , w 2 ) (a, b, w_1), (a, c, w_2) (a,b,w1),(a,c,w2)，那么可以得到状态 ( a , 4 x + 3 w 1 ) , ( a , 4 x + 3 w 2 ) (a, 4x + 3w_1), (a, 4x + 3w_2) (a,4x+3w1),(a,4x+3w2)，因此 ( a , x ) (a, x) (a,x) 和 ( a , x + 3 ( w 1 − w 2 ) ) (a, x + 3(w_1 - w_2)) (a,x+3(w1−w2)) 是互相可达的。显然这个连通块中任意一个点 p p p 都满足 ( p , x ) (p, x) (p,x) 和 ( p , x + 3 ( w 1 − w 2 ) ) (p, x + 3(w_1 - w_2)) (p,x+3(w1−w2)) 是互相可达的。
考虑如果一对边边权的差为 d d d，那么我可以让 ( p , x ) (p,x) (p,x) 到达 ( p , x + 3 d ) (p, x +3d) (p,x+3d) 。证明考虑从一条边到另外一条边的路径，不难用中间的点来得到这个差。
因此设所有边两两之差的最大公约数为 d d d，设 g = ( M O D , 3 d ) g = (MOD, 3d) g=(MOD,3d)，那么 ( p , x ) (p, x) (p,x) 和 ( p , x + g ) (p, x + g) (p,x+g) 都是可以互相到达的。
注意到此时任意一条边的边权为 k d + r kd + r kd+r。先考虑一下 r = 0 r = 0 r=0 怎么做。此时任意一个点的状态都可以表示为 t d td td，我们可以把值对 g g g 取模，因此我们只关心 t t t 对 3 3 3 取模后的余数。然后就是一个点数只有 3 n 3n 3n 的图判断连通性，直接并查集维护就行了。
现在考虑 r ≠ 0 r \neq 0 r=0 的情形。注意到所有边的 r r r 都是相同的，最终路径的权值是 ∑ i 2 i ( k i d + r ) = k d + ( 2 l − 1 ) r \sum_{i} 2^i (k_i d + r) = kd + (2^l- 1) r ∑i2i(kid+r)=kd+(2l−1)r 。现在比较难处理的问题是 2 l − 1 2^l - 1 2l−1。考虑左后横跳可以在不改变 k m o d 3 k\mod 3 kmod3 的情况下使得 l l l 增加 2。因此枚举 k k k 和 l l l 的奇偶性，判断是否存在一个 l l l 使得 k d + ( 2 l − 1 ) r = R kd + (2^l - 1) r = R kd+(2l−1)r=R。现在状态数只有 6 n 6n 6n 并查集维护即可。
