P2416 泡芙 题解

Acerkaio · 2023-03-07 20:26:31 · 题解

思路：

易知：此题在同一个边双连通分量中的每一条边都可以走一遍，我们遍可以将一个边双连通分量，缩成一个点，这个点的点权 w1_i 便是该边双连通分量边权和。

缩完之后，我们剩下的边都是割边，便是一颗树，那么 s 到 t 只会有一个简单路径，便是新图的 col_s 到 col_t，col_i 是 i 所在的边双中的代表元素，即为 col_s 到 lca_{col_s, col_t} 的边权和加上 col_t 到 lca_{col_s, col_t}的边权和，我们可以维护一个从根节点到每个点的边权和 w2_i 那么答案即为

CODE:

#include <bits/stdc++.h>
using namespace std;
const int _ = 1e6;

int head[_], tot = 1;
struct NODE {
    int x, y, edge, next;
} edge[_ << 1];

void add(int u, int v, int ed) {
    tot++;
    edge[tot].x = u;
    edge[tot].y = v;
    edge[tot].edge = ed;
    edge[tot].next = head[u];
    head[u] = tot;
}

int head1[_], thoth = 1;
struct ND {
    int x, y, edge, next;
} edge1[_ << 1];

void add1(int u, int v, int ed) {
    thoth++;
    edge1[thoth].x = u;
    edge1[thoth].y = v;
    edge1[thoth].edge = ed;
    edge1[thoth].next = head1[u];
    head1[u] = thoth;
}

int dfn[_], low[_], NOD, cut[_], w1[_], w2[_];
int col[_];
stack <int> lxq;
void Tarjan(int u, int ed) {
    dfn[u] = low[u] = ++NOD;
    lxq.push(u);
    for (int i = head[u], v; v = edge[i].y, i; i = edge[i].next) {
        if (!dfn[v]) {
            Tarjan(v, i);
            if (dfn[u] < low[v]) {
                cut[i] = cut[i ^ 1] = 1;
            }
            low[u] = min(low[u], low[v]);
        } else {
            if (i != (ed ^ 1)) {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }
    if (dfn[u] == low[u]) {
        while (lxq.top() != u) {
            col[lxq.top()] = u;
            lxq.pop();
        }
        col[lxq.top()] = u;
        lxq.pop();
    }
}

/*po*/

int fa[_], Hson[_], Dep[_], Size[_], Top[_], seg[_], rev[_], DFNtot = 0;
void Podfs1(int p, int f, int deg) {
    fa[p] = f;
    Dep[p] = Dep[f] + 1;
    Size[p] = 1;
    w2[p] += w1[p] + deg;
    for (int i = head1[p]; i; i = edge1[i].next) {
        int v = edge1[i].y;
        if (v == f) continue;
        Podfs1(v, p, w2[p] + edge1[i].edge);
        Size[p] += Size[v];
        if (Size[v] > Size[Hson[p]]) Hson[p] = v;
    }
}
void Podfs2(int p, int top) {
    ++DFNtot;
    Top[p] = top;
    seg[p] = DFNtot;
    rev[DFNtot] = p;
    if (Hson[p])
        Podfs2(Hson[p], top);
    for (int i = head1[p]; i; i = edge1[i].next) {
        int v = edge1[i].y;
        if (v == fa[p]) continue;
        if (Hson[p] != v) Podfs2(v, v);
    }
}

int LCA(int u, int v) {

    int fu = Top[u], fv = Top[v];
    while (fu != fv) {
//      cout << u << ' ' << v << '\n';
        if (Dep[fu] < Dep[fv]) swap(fu,fv), swap(u, v);
        u = fa[fu], fu = Top[u];
    }
    return Dep[u] < Dep[v] ? u : v;
}
signed main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) Tarjan(i, 0);
    for (int i = 1; i <= tot; i++) {
        int u = col[edge[i].x], v = col[edge[i].y], w = edge[i].edge;
        if (u == v) {
            w1[u] += w;
        } else {
            add1(u, v, w);
        }
    }

    Podfs1(1, 1, 0);
    Podfs2(1, 1);
    int q;
    cin >> q;

    for (int i = 1; i <= q; i++) {
        int x, y, lca;
        cin >> x >> y;
        //cout << x << ' ' << y << '\n'; 
        x = col[x], y = col[y];
//      cout << x << ' ' << y;
        lca = LCA(x, y);
        if (w2[x] + w2[y] - 2 * w2[lca] + w1[lca] > 0) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}