CF555E Case of Computer Network TJ
前置知识
-
树上差分
如果想对一条路径上的所有边 / 点同时加上一个相同的值（称为边 / 点差分），我们可以通过树上差分来达到 \(O(\log n)\) 修改，查询的时候 \(O(n)\) 做一遍子树和即可，这里只讲边差分。
如果我们想对 \((u, v)\) 这两个点之间的所有边都增加一个值 \(k\)。
\(d_u \rightarrow d_u + k\)，\(d_v \rightarrow d_v + k\)，\(d_{lca} \rightarrow d_{lca} - 2k\)
我们把边的权值下放到深度较深的的节点那。
仿照数组上差分，我们有 \(d_u + 1\) 相当于从根节点到 \(u\) 的路径上的所有边 \(+ 1\)。
现在再去理解上面三个式子就非常的简单了。
\(u \rightarrow v\) 相当于 \(u \rightarrow \operatorname{lca}(u, v) \rightarrow v\)。
思路
这里才是正解。
-
题意
给你一个无向图，让你对每条边定向。
要求满足 \(q\) 个 \((a, b)\)，问有没有一种方式使得对于每一组 \({(a, b)}\)，都能从 \(a\) 到达 \(b\)。
-
思路
有一个很漂亮的性质：在一个边双里的点一定可以通过某种定向来互相到达。
证明如下：
- 我们可以把删去那条边之后的边都按一个顺序连接，这个时候就会形似一个链，这时候再把那条边加上，就一定可以互相到达了（首连尾）。
这时候我们就可以把处于一个边双里的点缩成一个点，只考虑桥边的定向。我们就可以记两个数组 \(up\) 和 \(down\)。表示这条边是否需要向上跳。然后用树上差分快速修改即可。
如果不合法就一定是有一条边既要往上又要往下。
代码
#include <bits/stdc++.h>const int N = 2e5 + 10;struct E {int v;int nxt;
} e[N << 1]; int head[N], cnt;__inline void add(int u, int v) { e[cnt] = {v, head[u]}; head[u] = cnt++; }int dfn[N], low[N], bel[N], tot, bcc_cnt;
std::vector<int> stk;
std::vector<int> edge[N];__inline void Tarjan(int u, int from) {dfn[u] = low[u] = ++tot;stk.emplace_back(u);for (int i = head[u]; i != -1; i = e[i].nxt) {int v = e[i].v;if ((i ^ 1) == from) continue;if (!dfn[v]) {Tarjan(v, i);low[u] = std::min(low[u], low[v]); }else low[u] = std::min(low[u], dfn[v]);}if (low[u] == dfn[u]) {bcc_cnt++;int x;do {x = stk.back(); stk.pop_back();bel[x] = bcc_cnt;} while (x != u); }
}int dep[N], fa[N][25];
bool vis_dfs[N];
__inline void dfs(int u, int f) {vis_dfs[u] = true;dep[u] = dep[f] + 1;fa[u][0] = f;for (int i = 0; fa[u][i]; i++) fa[u][i + 1] = fa[fa[u][i]][i];for (int v : edge[u])if (v != f && !vis_dfs[v])dfs(v, u);
}__inline int lca(int u, int v) {if (dep[u] < dep[v]) std::swap(u, v);for (int i = 21; ~i; i--) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];if (u == v) return u;for (int i = 21; ~i; i--)if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];return fa[u][0];
}int faa[N];
__inline int find(int x) { return faa[x] = (faa[x] == x ? x : find(faa[x])); }
__inline void merge(int u, int v) { if (find(u) != find(v)) faa[find(u)] = find(v); }int up[N], down[N];
bool vis_sum[N];
__inline void modify(int u, int v, int *arr) {int L = (dep[u] < dep[v] ? u : v);arr[u] += 1;arr[v] += 1;arr[L] -= 2;
}__inline void get_sum(int u, int f) {vis_sum[u] = true;for (int v : edge[u]) {if (v != f && !vis_sum[v]) {get_sum(v, u);down[u] += down[v];up[u] += up[v];}}
}bool vis_check[N];
void check(int u, int f) {vis_check[u] = true;for (int v : edge[u]) {if (v == f) continue;if (up[v] > 0 && down[v] > 0) {std::cout << "No\n";exit(0);}if (!vis_check[v])check(v, u);}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);memset(head, -1, sizeof head);int n, m, q;std::cin >> n >> m >> q;for (int i = 1; i <= m; i++) {int u, v;std::cin >> u >> v;add(u, v);add(v, u);}for (int i = 1; i <= n; i++)if (!dfn[i])Tarjan(i, -1); for (int i = 1; i <= bcc_cnt; i++)faa[i] = i;for (int u = 1; u <= n; u++) {for (int id = head[u]; ~id; id = e[id].nxt) {int v = e[id].v;if (bel[v] == bel[u]) continue;edge[bel[u]].emplace_back(bel[v]);edge[bel[v]].emplace_back(bel[u]);merge(bel[u], bel[v]);}}for (int i = 1; i <= bcc_cnt; i++)if (!vis_dfs[i])dfs(i, 0);for (int i = 1; i <= q; i++) {int u, v;std::cin >> u >> v;int ndu = bel[u], ndv = bel[v];if (ndu == ndv) continue;if (find(ndu) != find(ndv)) {std::cout << "No\n";return 0; }else {int L = lca(ndu, ndv);if (ndu == L) modify(ndu, ndv, down);else if (ndv == L) modify(ndu, ndv, up);else { modify(ndu, L, up); modify(L, ndv, down); }}}for (int i = 1; i <= bcc_cnt; i++)if (!vis_sum[i]) get_sum(i, 0);for (int i = 1; i <= bcc_cnt; i++)if (!vis_check[i]) check(i, 0);std::cout << "Yes\n";return 0;
}
不要在意奇奇怪怪的码风 / __inline。