扫地机器人 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 500000 + 100;
const int Log = 40;
int n, v, u, ans, numN;
int t[maxn], deg[maxn], cnt[maxn], sum[maxn], mx[maxn], ppos[maxn], ssum[maxn];
int dpp[maxn], last[maxn];
vector<int> dp[maxn];
bool vis[maxn], hasTree[maxn];
vector<int> G[maxn];
queue<int> que;
int stmax[maxn][Log], mn[maxn];

void Init(int n) {
    mn[0] = -1;
    for(int i = 1; i <= n; ++i) {
        mn[i] = ((i & (i - 1)) == 0)? mn[i - 1] + 1: mn[i - 1];
        stmax[i][0] = ssum[i];
    }
    for(int j = 1; j <= mn[n]; ++j) {
        for(int i = 1; i + (1 << j) - 1 <= n; ++i) {
            stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int rmqMax(int L, int R) {
    int k = mn[R - L + 1];
    return max(stmax[L][k], stmax[R - (1 << k) + 1][k]);
}

bool cmp(int a, int b) {
    return a > b;
}

void dfs(int root, int fa) {
    ppos[++numN] = root;
    vis[root] = true;
    for (int pos : G[root]) {
        if (pos != fa && !vis[pos]) {
            dfs(pos, root);
        }
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        ++deg[u];
        ++deg[v];
    }
    for (int i = 1; i <= n; ++i) {
        if (deg[i] == 1) {
            --deg[i];
            que.push(i);
            vis[i] = true;
            dpp[i] = t[i];
        }
    }
    while (!que.empty()) {
        int tmp = que.front();
        que.pop();
        for (int pos : G[tmp]) {
            if (vis[pos]) {
                continue;
            }
            dp[pos].push_back(dpp[tmp]);
            hasTree[pos] = true;
            --deg[pos];
            if (deg[pos] == 1) {
                que.push(pos);
                vis[pos] = true;
                sort(dp[pos].begin(), dp[pos].end(), cmp);
                if (dp[pos].size() >= 2) {
                    ans = max(ans, t[pos] + dp[pos][0] + dp[pos][1]);
                }
                dpp[pos] = t[pos] + dp[pos][0];
            }
        }
    }
    int loopSum = 0;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            loopSum += t[i];
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            sort(dp[i].begin(), dp[i].end(), cmp);
            if (dp[i].size() > 0) {
                ans = max(ans, dp[i][0] + loopSum);
                mx[i] = dp[i][0];
            }
            if (dp[i].size() > 1) {
                ans = max(ans, dp[i][1] + dp[i][0] + loopSum);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dfs(i, i);
        }
    }
    for (int i = 0; i < numN; ++i) {
        ppos[i + numN + 1] = ppos[i + 1];
    }
    int sumTmp = 0;
    for (int i = 1; i <= numN * 2; ++i) {
        sumTmp += t[ppos[i]];
        ssum[i] = sumTmp + mx[ppos[i]];
    }
    Init(numN * 2);
    int lastHasTree = 0;
    for (int i = 1; i <= numN * 2; ++i) {
        if (hasTree[ppos[i]]) {
            lastHasTree = i;
        }
        last[i] = lastHasTree;
    }
    sumTmp = 0;
    for (int i = 1; i <= numN; ++i) {
        sumTmp += t[ppos[i]];
        if (hasTree[i]) {
            lastHasTree = last[i + numN - 1];
            if (lastHasTree != i) {
                ans = max(ans, t[ppos[i]] + mx[ppos[i]] + rmqMax(i + 1, lastHasTree) - sumTmp);
            }
        }
    }
    cout << ans << endl;

    return 0;
}