题解：P13542 [OOI 2022] Two avenues

· · 题解

P13542 [OOI 2022] Two avenues

考虑发现：若删除两条边后点对 (a,b) 不再联通，则它们必然会带来贡献，于是我们考虑删除边之后会分成多个连通块，不然不会带来任何贡献。

若原图是树即 sub 5，则每个边都是一个桥，树上唯一路径经过这个边的两个点必然会带来 1 的贡献，于是这个 sub 可以用 lca + 树上差分解决。

考虑普通的状态，我们发现可以建一颗 dfs 树，然后对不同的两个边的选择进行考虑：

  1. 我们选了两个桥，则答案就是分别经过这两条边的点对 (a,b) 的个数的和，即 c_u+c_v。

  2. 我们选择一个桥和一个任意的边，则就是 c_u。

  3. 我们选择一个非桥的树边和一个非树边，我们设一个树边的集合 S 表示有什么非树边包裹着它，则我们需要这个树边的集合 S 恰好是我们选择的非树边，不然原图依然联通。

  4. 我们要选择两个非桥的树边。可以发现它们必然需要是祖先关系。这个时候我们需要 S_u=S_v，不然若两者被覆盖的非树边集合不同，则删去后 subtree_u\setminus subtree_v 的位置会和上面或者下面再次联通，没有用处。

于是我们推出了这样的条件。但是这个集合相等明显不好维护，我们可以联想到随机化哈希判定集合相等，对每个树边附上一个权值，然后树上差分即可得到每个树边的集合的权值和，即可快速判定。

考虑计算情况 4 的贡献总数。其实就是居民的起点和终点有一点在 subtree_u\setminus subtree_v 内而另一点在外。考虑换一种方式表示：

我们设 c_u 表示 u 节点对应的边中有多少个市民的树上路径经过了它，则答案可以转换为恰好经过一个 u 和 v 中的边的方案数，也就是 c_u+c_v-2\times g(u,v)，其中 g(u,v) 表示同时经过了 u 和 v 对应的边的居民个数。

考虑如何快速求出 g(u,v)：也就是需要 dfn_a\in[L_v,R_v] 且 dfn_b\not \in [L_u,R_u]，用主席树维护 (dfn_a, dfn_b) 和 (dfn_b, dfn_a) 即可。

但是这样方案 4 的枚举依然是 n^2\log n 的，我们发现将方案 4 分组后按深度从上到下考虑，是有决策单调性 opt_i\le opt_j 的，于是我们可以决策单调性分治，时间复杂度 O(n\log^2n)。

:::success[Code]

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N = 5e5 + 10, M = N * 40;
mt19937_64 rng(114514);
int n, m, K, eu[N], ev[N];
ull ew[N], xr[N];
vector<int> pt[N];
int fa[N], fid[N], dep[N], L[N], R[N], dfn_cnt;
struct edge {int v, id;};
vector<edge> g[N];
void dfs(int u, int f, int fp) {
    fa[u] = f; fid[u] = fp;
    dep[u] = dep[f] + 1;
    L[u] = ++dfn_cnt;
    for(auto e: g[u]) {
        int v = e.v, id = e.id;
        if(id == fp) continue;
        if(!L[v]) {
            dfs(v, u, id);
            xr[u] ^= xr[v];
        }
        else if(dep[v] < dep[u]) {
            if(!ew[id]) ew[id] = rng();
            xr[u] ^= ew[id], xr[v] ^= ew[id];
        }
    }
    R[u] = dfn_cnt;
}
int sum[M], ls[M], rs[M], rt[N], tot;
int c[N];
void insert(int &cur, int pre, int l, int r, int pos) {
    cur = ++tot;
    ls[cur] = ls[pre], rs[cur] = rs[pre];
    sum[cur] = sum[pre] + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(pos <= mid) insert(ls[cur], ls[pre], l, mid, pos);
    else insert(rs[cur], rs[pre], mid + 1, r, pos);
}
int query(int p, int q, int l, int r, int ql, int qr) {
    if(!p || (ql <= l && r <= qr)) return sum[p] - sum[q];
    int mid = l + r >> 1, res = 0;
    if(ql <= mid) res = query(ls[p], ls[q], l, mid, ql, qr);
    if(qr > mid) res += query(rs[p], rs[q], mid + 1, r, ql, qr);
    return res;
}
int both(int u, int v) {
    return sum[rt[R[v]]] - sum[rt[L[v] - 1]] - query(rt[R[v]], rt[L[v] - 1], 1, n, L[u], R[u]);
}
int ans, ans1, ans2;
void upd(int val, int e1, int e2) {
    if(val > ans) ans = val, ans1 = e1, ans2 = e2;
}
vector<int> vv;
void solve(int l, int r, int ql, int qr) {
    if(l > r || ql > qr) return;
    int mid = l + r >> 1;
    int mx = -1, pos = max(mid + 1, ql), u = vv[mid];
    for(int i = pos; i <= qr; i++) {
        int v = vv[i], val = c[u] + c[v] - 2 * both(u, v);
        if(val > mx) mx = val, pos = i;
    }
    if(mx != -1) upd(mx, fid[u], fid[vv[pos]]);
    solve(l, mid - 1, ql, pos); solve(mid + 1, r, pos, qr);
    return;
}
void Solve() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) g[i].clear(), pt[i].clear(), L[i] = xr[i] = 0;
    dfn_cnt = tot = 0;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &eu[i], &ev[i]), ew[i] = 0;
        g[eu[i]].push_back({ev[i], i}), g[ev[i]].push_back({eu[i], i});
    }
    dfs(1, 0, 0);
    scanf("%d", &K);
    for(int i = 1; i <= K; i++) {
        int a, b; scanf("%d%d", &a, &b);
        pt[L[a]].push_back(L[b]);
        pt[L[b]].push_back(L[a]);
    }
    for(int i = 1; i <= n; i++) {
        rt[i] = rt[i - 1];
        for(auto x : pt[i]) insert(rt[i], rt[i], 1, n, x);
    }
    ans = 0, ans1 = 1, ans2 = 2;
    vector<pair<int, int>> br;
    vector<pair<ull, int>> bk;
    vector<tuple<ull, int, int>> tr;
    for(int i = 1; i <= m; i++) if(ew[i]) bk.push_back({ew[i], i});
    sort(bk.begin(), bk.end());
    for(int u = 2; u <= n; u++) {
        c[u] = both(u, u);
        if(!xr[u]) br.push_back({c[u], fid[u]});
        else {
            tr.emplace_back(xr[u], dep[u], u);
            auto it = lower_bound(bk.begin(), bk.end(), make_pair(xr[u], 0));
            if(it != bk.end() && it -> first == xr[u]) upd(c[u], fid[u], it -> second);
        }
    }
    sort(br.rbegin(), br.rend());
    if(!br.empty()) upd(br[0].first, br[0].second, br[0].second == 1 ? 2 : 1);
    if(br.size() > 1) upd(br[0].first + br[1].first, br[0].second, br[1].second);
    sort(tr.begin(), tr.end());
    for(int i = 0, j = 0; i < (int)tr.size(); i = j) {
        j = i; vv.clear();
        while(j < (int)tr.size() && get<0>(tr[j]) == get<0>(tr[i])) vv.push_back(get<2>(tr[j++]));
        if(vv.size()) solve(0, (int)vv.size() - 2, 1, (int)vv.size() - 1);
    }
    printf("%d\n%d %d\n%d %d\n", ans, eu[ans1], ev[ans1], eu[ans2], ev[ans2]);
}
int main() {
    int T, Ca; scanf("%d%d", &T, &Ca);
    while(T--) Solve();
    return 0;
}