给定一张N个顶点M条边的无向图(顶点编号为1,2,…,ak的最小公倍数是能被每个ai整除的最小正整数, 路径:路径P:P1,P2,…,Pk是顶点序列,满足对于任意1 ≤ i < k,节点Pi和Pi+1之间都有边相连, 简单路径:如果路径P:P1,P2,…
给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n),每条边上带有权值。所有权值都可以分解成2^a*3^b 的形式。 现在有q个询问,每次询问给定四个参数u、v、a和b,请你求出是否存在一条顶点u到v之间的路径,使得 路径依次经过的边上的权值的最小公倍数为2^a*3^b。 注意:路径可以不是简单路径。 下面是一些可能有用的定义 : 最小公倍数:K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。 路径:路径P:P1,P2,…,Pk是顶点序列,满足对于任意1 ≤ i < k,节点Pi和Pi+1之间都有边相连。 简单路径:如果路径P:P1,P2,…,Pk中,对于任意1 ≤ s≠t ≤ k都有Ps≠Pt,那么称路径为简单路径。
(图片来源网络,侵删)