题目描述
给定一张 \(n\) 个点的无向图，刚开始为空。执行 \(m\) 次操作 \((3\) 种操作\()\)。
-
1 u v w，在点 \(u\) 与点 \(v\) 之间加入一条权值为 \(w\) 的边。 -
2 id，删除第 \(id\) 次操作加入的边。 -
3 u v w，询问点 \(u\) 与点 \(v\) 之间是否存在一条权值模 \(F\) 为 \(w\) 的路径 \((\)不一定要为简单路径\()\)。
\(1\le n,m\le 10^5,1\le F\le 10^9\)。
显然可以按时间分治建立线段树，可以参考 线段树分治模板。
考虑如何判断模 \(F\) 为 \(w\) 的路径。
如果询问的 \(x,y\) 不在同一个连通块内则必然无解。否则 \(x,y\) 之间的路径权值和必定可以表示为 \(L+k\cdot G(\text{mod }F)\)，\(L\) 表示 \(x,y\) 之间固定的一条路径权值和，\(G\) 表示 \(x,y\) 所在连通块的所有环的长度和 \(F\) 的最大公约数。
若能证明任意一条路径权值和能表示成固定的一条路径权值和 \(L\) 和若干倍环长最大公约数 \(G\)，就可以轻松维护。
考虑两条 \(x,y\) 之间不同的路径的对称差中，一定每个点的度数都是偶数，所以可以将其拆分成若干个环。那么就可以通过环来使得任意两种不同的路径相互转化。
所以就只需要维护环长最大公约数以及任意一条路径长度。
如果加入的边连接的是在同一连通块的 \(x,y\)，则环长的最大公约数 \(G\) 更新为 \(\gcd(G,2w,w+L(x)+L(y))\)。其中 \(L(x)\) 表示 \(x\) 到并查集中 \(x\) 的根的距离。
否则环长的最大公约数 \(G\) 更新为 \(\gcd(G_x,G_y,2w)\)，其中 \(G_x\) 表示 \(x\) 所在连通块的环长的最大公约数。
使用按秩合并的并查集以及线段树合并进行维护即可，时间复杂度 \(O(n\log n\log m)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
struct Edge{ int x, y, w; } edge[N];
struct dsu{ int ty, x; ll w; } s[N * 36];
int n, m, F, top, op[N], fa[N], sz[N], del[N]; ll d[N], G[N];
vector <Edge> tree[N << 2];
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline int find(int x) { return fa[x] == x ? fa[x] : find(fa[x]); }
inline ll D(int x) { ll ans = 0; while (fa[x] != x) ans += d[x], x = fa[x]; return ans; }
inline void merge(int x, int y, int z) {
int fx = find(x), fy = find(y);
if (fx == fy) {
s[++ top] = (dsu) {1, fx, G[fx]};
G[fx] = gcd(G[fx], D(x) + D(y) + z);
G[fx] = gcd(G[fx], z + (x != y) * z);
} // at the same block
else {
if (sz[fx] > sz[fy]) swap(fx, fy);
s[++ top] = (dsu) {1, fy, G[fy]};
s[++ top] = (dsu) {2, fx, fy};
fa[fx] = fy, d[fx] = z - D(x) - D(y), sz[fy] += sz[fx];
G[fy] = gcd(G[fy], G[fx]);
G[fy] = gcd(G[fy], z + z);
} // at the different block
}
inline void split(int id) {
dsu o = s[id];
if (o.ty == 1) G[o.x] = o.w; // delete an edge in a block
else fa[o.x] = o.x, d[o.x] = 0, sz[o.w] -= sz[o.x]; // delete an edge to get two blocks
} // delete idth operation
inline void add(int x, int l, int r, int L, int R, Edge v) {
if (L <= l && R >= r) return void(tree[x].emplace_back(v));
int mid = l + r >> 1;
if (L <= mid) add(x << 1, l, mid, L, R, v);
if (R > mid) add(x << 1 | 1, mid + 1, r, L, R, v);
}
inline void query(int id) {
Edge pr = edge[id];
int fx = find(pr.x), fy = find(pr.y), ans = 0;
if (fx == fy) {
int g = gcd(G[fx], F);
if (g) if ((pr.w - D(pr.x) - D(pr.y)) % g == 0) ans = 1;
}
cout << ans << '\n';
}
inline void solve(int x, int l, int r) {
int sz = top;
for (Edge v : tree[x]) merge(v.x, v.y, v.w);
if (l == r && op[r] == 3) query(r);
if (l < r) {
int mid = l + r >> 1;
solve(x << 1, l, mid), solve(x << 1 | 1, mid + 1, r);
}
while (top > sz) split(top --);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> F;
for (int i = 1; i <= n; ++ i) fa[i] = i, sz[i] = 1;
for (int i = 1; i <= m; ++ i) {
int type; cin >> type; op[i] = type;
if (type == 1) {
int x, y, w; cin >> x >> y >> w;
edge[i] = (Edge) {x, y, w};
} else if (type == 2) {
int id; cin >> id;
add(1, 1, m, id, i - 1, edge[id]);
del[id] = 1;
} else {
int x, y, w; cin >> x >> y >> w;
edge[i] = (Edge) {x, y, w};
}
}
for (int i = 1; i <= m; ++ i) if (op[i] == 1 && !del[i]) add(1, 1, m, i, m, edge[i]);
solve(1, 1, m);
return 0;
}