AOJ 2712 Escape (JAG 夏合宿 2015 day2-G) (500 点)

こどふぉでまったく同じ問題が出た！！！
始点の入力の仕方が異なるのみ (こっちでは始点はノード 1 に固定、こどふぉでは始点 s を入力で与える)

drken1215.hatenablog.com

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M, S = 0;
vector<long long> w;
using Graph = vector<vector<int> >;
Graph G;

void dfs(vector<int> vs, vector<long long> &dist) {
    for (auto v : vs) {
        for (auto nv : G[v]) {
            if (dist[nv] != -1) continue;
            dist[nv] = dist[v] + w[nv];
            dfs({nv}, dist);
        }
    }
}

long long solve() {
    vector<int> deg(N, 0);
    for (int v = 0; v < N; ++v) {
        for (auto nv : G[v]) {
            ++deg[v];
            ++deg[nv];
        }
    }
    for (int v = 0; v < N; ++v) deg[v] /= 2;

    queue<int> que;
    for (int v = 0; v < N; ++v) if (v != S && deg[v] == 1) que.push(v);

    vector<bool> fucked(N, false);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        fucked[v] = true;
        for (auto nv : G[v]) {
            --deg[nv];
            if (nv != S && deg[nv] == 1) que.push(nv);
        }
    }

    long long res = 0;
    vector<int> vs;
    vector<long long> dist(N, -1);
    for (int v = 0; v < N; ++v) if (!fucked[v]) {
            res += w[v];
            vs.push_back(v);
            dist[v] = 0;
        }

    dfs(vs, dist);
    long long ma = 0;
    for (int v = 0; v < N; ++v) ma = max(ma, dist[v]);
    return res + ma;
}


int main() {
    cin >> N >> M;
    w.resize(N);
    for (int i = 0; i < N; ++i) cin >> w[i];
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    cout << solve() << endl;
}