TIOJ 2031：盩僰麌在做 弢哥在看

TIOJ 2031：盩僰麌在做 弢哥在看

題目大意：有 $n$ 個點，編號 $1\sim n$，每個點有一值 $a_i$，每個 $i$ 可以向編號比自己小的點連 $L_i$ 條單向邊，向編號比自己大的點連 $R_i$ 條單向邊，連的順序優先連向與 $a_i\ \text{xor}$ 值較大者。建好邊後，給一個出發點 $s$，問所有走到的點權重和最大可以是多少。

解法：先用類似 $\text{trie}$ 的概念建好邊，再用 $\text{tarjan SCC}$ 縮點後 $\text{DP}$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5e5 + 5;
const int H = __lg (SIZE) + 2;

int n, s;
int a[SIZE], l[SIZE], r[SIZE];
vector<int> adj[SIZE];

int to[5 * SIZE][2], id[5 * SIZE], siz[5 * SIZE], cnt = 1;

void update (int i) {
    int node = 1;
    for (int t = H; t >= 0; t--) {
        bool b = (a[i] >> t) & 1;
        if (!to[node][b])
            to[node][b] = ++cnt;
        siz[to[node][b]]++;
        node = to[node][b];
    }
    id[node] = i;
}

void add (int i, int k, int node, int dep) {
    if (k == 0)
        return;
    if (dep == -1) {
        adj[i].pb (id[node]);
        return;
    }
    int b = (a[i] >> dep) & 1;
    if (!to[node][b ^ 1])
        add (i, k, to[node][b], dep - 1);
    else if (siz[to[node][b ^ 1]] >= k)
        add (i, k, to[node][b ^ 1], dep - 1);
    else {
        add (i, siz[to[node][b ^ 1]], to[node][b ^ 1], dep - 1);
        add (i, k - siz[to[node][b ^ 1]], to[node][b], dep - 1);
    }
}

int dfcnt, dfn[SIZE], low[SIZE];
vector<int> st, scc_adj[SIZE];
bool ist[SIZE];
int sccnt, scc[SIZE];
long long sum[SIZE], dp[SIZE];

void tarjan (int pos) {
    dfn[pos] = low[pos] = ++dfcnt;
    st.pb (pos), ist[pos] = 1;
    for (int np : adj[pos]) {
        if (!dfn[np]) {
            tarjan (np);
            low[pos] = min (low[pos], low[np]);
        } else if (ist[np])
            low[pos] = min (low[pos], dfn[np]);
    }
    if (low[pos] == dfn[pos]) {
        sccnt++;
        while (1) {
            scc[st.back()] = sccnt;
            ist[st.back()] = 0;
            sum[sccnt] += a[st.back()];
            if (st.back() == pos) {
                st.pop_back();
                break;
            }
            st.pop_back();
        }
    }
}

long long dfs (int pos) {
    if (dp[pos] >= 0)
        return dp[pos];
    long long mx = 0;
    for (int np : scc_adj[pos])
        mx = max (mx, dfs (np));
    return dp[pos] = sum[pos] + mx;
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    cin >> n >> s;
    FOR (i, 1, n) cin >> a[i];
    FOR (i, 1, n) cin >> l[i] >> r[i];
    FOR (i, 1, n) {
        add (i, l[i], 1, H);
        update (i);
    }
    fill (to[0], to[cnt] + 2, 0);
    fill (siz, siz + cnt + 1, 0);
    fill (id, id + cnt + 1, 0);
    cnt = 1;
    for (int i = n; i >= 1; i--) {
        add (i, r[i], 1, H);
        update (i);
    }
    FOR (i, 1, n) {
        if (!dfn[i])
            tarjan (i);
        dp[i] = -1;
    }
    FOR (i, 1, n) {
        for (int np : adj[i]) {
            if (scc[i] != scc[np])
                scc_adj[scc[i]].pb (scc[np]);
        }
    }
    cout << dfs (scc[s]) << '\n';
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！