Description
給定一張 N N 個頂點 MM 條邊的無向圖(頂點編号為 1,2,…,n 1 , 2 , … , n ),每條邊上帶有權值。所有權值都可以分解成 2a×3b 2 a × 3 b 的形式。現在有 q q 個詢問,每次詢問給定四個參數 uu 、 v v 、 aa 和 b b ,請你求出是否存在一條頂點 uu 到 v v 之間的路徑,使得路徑依次經過的邊上的權值的最小公倍數為 2a×3b2a×3b 。注意:路徑可以不是簡單路徑。
下面是一些可能有用的定義:
最小公倍數: K K 個數 a1,a2,…,aka1,a2,…,ak 的最小公倍數是能被每個 ai a i 整除的最小正整數。
路徑:路徑 P:P1,P2,…,Pk P : P 1 , P 2 , … , P k 是頂點序列,滿足對于任意 1≤i<k 1 ≤ i < k ,節點 Pi P i 和 Pi+1 P i + 1 之間都有邊相連。
簡單路徑:如果路徑 P:P1,P2,…,Pk P : P 1 , P 2 , … , P k 中,對于任意 1≤s≠t≤k 1 ≤ s ≠ t ≤ k 都有 Ps≠Pt P s ≠ P t ,那麼稱路徑為簡單路徑。
Input
輸入檔案的第一行包含兩個整數 N N 和 MM ,分别代表圖的頂點數和邊數。接下來 M M 行,每行包含四個整數 uu 、 v v 、 aa 、 b b 代表一條頂點 uu 和 v v 之間、權值為 2a×3b2a×3b 的邊。接下來一行包含一個整數 q q ,代表詢問數。接下來 qq 行,每行包含四個整數 u u 、 vv 、 a a 和 bb ,代表一次詢問。詢問内容請參見問題描述。
1≤n,q≤50000,1≤m≤100000,0≤a,b≤109 1 ≤ n , q ≤ 50000 , 1 ≤ m ≤ 100000 , 0 ≤ a , b ≤ 10 9
Output
對于每次詢問,如果存在滿足條件的路徑,則輸出一行Yes,否則輸出一行No(注意:第一個字母大寫,其餘字母小寫) 。
Sample Input
4 5
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4
Sample Output
Yes
Yes
Yes
No
No
Solution
題意就是一個圖,每條邊上有 2 2 個權值 a,ba,b ,每次詢問是否有一條 u u 到 vv 的路徑(不一定是簡單路徑),使得路徑上的 a a 的最大值和 bb 的最大值恰好等于一個給定的值。
考慮一個暴力的 O((n+m)q) O ( ( n + m ) q ) 算法:
維護一個帶權并查集,維護每個連通塊的 a a 最大值和 bb 最大值。
對于一個詢問 (u,v,A,B) ( u , v , A , B ) ,初始化并查集,并将所有滿足 a≤A,b≤B a ≤ A , b ≤ B 的邊加入,最後詢問 u u 和 vv 是否連通,以及連通塊的最大值是否為 A,B A , B 。
考慮使用分塊優化。
先将所有的邊按照 a a 從小到大排序,分成 m−−√m 塊,然後在每一塊内按照 b b 排序。
那麼對于一個詢問,滿足條件的邊一定是這樣分布的(紅色部分):
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2LcRTW65UeNpWZ1g2MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2LcRHelR3LcJzLctmch1mclRXY39jNygTNzETMxETOyQDM4EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
即合法的邊分布在前 kk 塊,前 k−1 k − 1 塊中合法的邊在塊内是一個字首,在第 k k 塊中是零散的。
是以,可以把詢問按照 kk 進行分組,對每組詢問分類處理。
假設現在處理到第 k k 組詢問,則将詢問按照 BB 從小到大排序。
按照 B B 從小到大排序之後,對于前 k−1k−1 塊中選出的邊,選到的右邊界是遞增的,是以用 k−1 k − 1 個指針維護前 k−1 k − 1 塊取到的右邊界即可。
第 k k 塊是零散的,暴力加邊。但由于不同詢問中第 kk 塊内選出的邊不同,是以要寫一個可持久化支援撤回上一次操作的并查集。
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std;
inline int read() {
int res = ; bool bo = ; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = ; else res = c - ;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << ) + (res << ) + (c - );
return bo ? ~res + : res;
}
const int N = + , M = + , L = + , Sqrt = ;
int n, m, q, S, fa[N], max2[N], max3[N], QAQ, QWQ, l[Sqrt], r[Sqrt], cnt,
pos[Sqrt], tot, que[M], mina[Sqrt];
bool vis[M], ans[M];
struct cyx {int t, u, f, u2, u3, f2, f3;} o[L];
struct pyz {int u, v, a, b, id;} e[M], c[M];
inline bool comp1(const pyz &x, const pyz &y) {return x.a < y.a;}
inline bool comp2(const pyz &x, const pyz &y) {return x.b < y.b;}
inline int cx(const int &x, const bool &op) {
if (!op) {int y = x; while (fa[y] != y) y = fa[y]; return y;}
if (fa[x] != x) o[++QAQ] = (cyx) {QWQ, x, fa[x], -, -, -, -}
, fa[x] = cx(fa[x], ); return fa[x];
}
inline void zm(const int &x, const int &y, const int &a, const int &b) {
QWQ++; int ix = cx(x, ), iy = cx(y, );
if (ix != iy) o[++QAQ] = (cyx) {QWQ, iy, ix, max2[iy], max3[iy],
max2[ix], max3[ix]}, fa[iy] = ix, max2[ix] =
max(max(max2[ix], max2[iy]), a), max3[ix] = max(max(max3[ix],
max3[iy]), b), max2[iy] = max3[iy] = -;
else o[++QAQ] = (cyx) {QWQ, ix, -, max2[ix], max3[ix], -, -},
max2[ix] = max(max2[ix], a), max3[ix] = max(max3[ix], b);
}
inline void backto(const int &t) {
while (o[QAQ].t > t) {
if (o[QAQ].f == -) max2[o[QAQ].u] = o[QAQ].u2,
max3[o[QAQ].u] = o[QAQ].u3;
else {
fa[o[QAQ].u] = o[QAQ].u2 == - ? o[QAQ].f : o[QAQ].u;
if (o[QAQ].u2 != -) {
max2[o[QAQ].u] = o[QAQ].u2; max3[o[QAQ].u] = o[QAQ].u3;
max2[o[QAQ].f] = o[QAQ].f2; max3[o[QAQ].f] = o[QAQ].f3;
}
}
QAQ--;
}
QWQ = t;
}
int main() {
int i, j, k; n = read(); m = read();
For (i, , m) e[i].u = read(), e[i].v = read(),
e[i].a = read(), e[i].b = read();
q = read(); For (i, , q) c[i].u = read(), c[i].v = read(),
c[i].a = read(), c[i].b = read(), c[i].id = i; S = sqrt(m);
sort(e + , e + m + , comp1);
for (i = ; i <= m; i += S) l[++cnt] = i, r[cnt] = min(m, i + S - ),
mina[cnt] = e[l[cnt]].a; For (i, , cnt)
sort(e + l[i], e + r[i] + , comp2); sort(c + , c + q + , comp2);
For (i, , cnt) {
For (j, , n) fa[j] = j, max2[j] = max3[j] = -; QAQ = QWQ = tot = ;
For (j, , i - ) pos[j] = l[j]; For (j, , q)
if (!vis[j] && (i == cnt || mina[i + ] > c[j].a))
vis[que[++tot] = j] = ;
For (j, , tot) {
For (k, , i - ) while (pos[k] <= r[k] && e[pos[k]].b <= c[que[j]].b)
zm(e[pos[k]].u, e[pos[k]].v, e[pos[k]].a, e[pos[k]].b), pos[k]++;
int tmp = QWQ; For (k, l[i], r[i])
if (e[k].a <= c[que[j]].a && e[k].b <= c[que[j]].b)
zm(e[k].u, e[k].v, e[k].a, e[k].b);
int x = cx(c[que[j]].u, ), y = cx(c[que[j]].v, );
ans[c[que[j]].id] = x == y && max2[x] == c[que[j]].a
&& max3[y] == c[que[j]].b; backto(tmp);
}
}
For (i, , q) puts(ans[i] ? "Yes" : "No");
return ;
}