library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub shibh308/library

:heavy_check_mark: verify/lowlink_tree.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0415"
#include <bits/stdc++.h>

using namespace std;

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


#include "../lib/classes/lowlink.cpp"
#include "../lib/functions/twoedgeconnectedcomponents_tree.cpp"

signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<int> u(m), v(m);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    vector<vector<int>> edges(n);
    for(int i = 0; i < m; ++i){
        cin >> u[i] >> v[i];
        --u[i], --v[i];
        edges[u[i]].push_back(v[i]);
        edges[v[i]].push_back(u[i]);
    }
    auto res = two_edge_connected_components_tree(edges);
    int k = res.group_cnt;
    vector<int> values(k, 0);
    for(int i = 0; i < n; ++i)
        values[res.group[i]] += a[i];

    auto& par = res.par;
    auto& childs = res.childs;
    vector<int> dp(k, 0);
    vector<unordered_map<int, int>> dp2(k);
    function<void(int)> f = [&](int x){
        int val = 0;
        for(auto y : childs[x]){
            f(y);
            chmax(val, dp[y]);
        }
        dp[x] = values[x] + val;
    };
    f(0);

    int ans = 0;
    function<void(int)> g = [&](int x){
        multiset<int> v{0, 0};
        for(auto y : childs[x]){
            v.insert(dp[y]);
            v.erase(v.begin());
            g(y);
        }
        chmax(ans, values[x] + *prev(v.end()) + *prev(v.end(), 2));
    };
    g(0);
    cout << ans << endl;

    return 0;
}
#line 1 "verify/lowlink_tree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0415"
#include <bits/stdc++.h>

using namespace std;

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


#line 1 "lib/classes/lowlink.cpp"
struct LowLink{
    vector<vector<int>>& edges;
    // 関節点
    vector<int> art;
    vector<pair<int,int>> bridge;

    vector<int> used, ord, low;
    int k;

    void dfs(int idx, int par){
        ord[idx] = k++;
        low[idx] = ord[idx];
        bool is_art = false;
        int cnt = 0;
        for(auto& to : edges[idx]){
            if(ord[to] == -1){
                ++cnt;
                dfs(to, idx);
                low[idx] = min(low[idx], low[to]);
                is_art |= par != -1 && low[to] >= ord[idx];
                if(ord[idx] < low[to])
                    bridge.emplace_back(idx, to);
            }else if(to != par)
                low[idx] = min(low[idx], ord[to]);
        }
        is_art |= (par == -1 && cnt > 1);
        if(is_art)
            art.emplace_back(idx);
    }

    LowLink(vector<vector<int>>& edges) :
        edges(edges),
        ord(edges.size(), -1),
        low(edges.size(), 0),
        k(0)
    {
        for(int i = 0; i < edges.size(); ++i)
            if(ord[i] == -1)
                dfs(i, -1);
        for(auto& b : bridge)
            b = make_pair(min(b.first, b.second), max(b.first, b.second));
        sort(art.begin(), art.end());
        sort(bridge.begin(), bridge.end());
    }
};

#line 1 "lib/functions/twoedgeconnectedcomponents_tree.cpp"
struct Result{
    int group_cnt;
    vector<int> group;
    vector<vector<int>> group_elm_list;
    // 同じ二重辺連結成分の辺をグループごとに列挙する, 片方向のみ(辺数倍化しない)
    vector<vector<pair<int,int>>> same_group_edges;
    // 橋, 片方向のみ
    vector<pair<int,int>> bridges;
    // 関節点
    vector<int> arts;
    vector<vector<int>> tree_graph;
    vector<int> par;
    vector<vector<int>> childs;
};

Result two_edge_connected_components_tree(vector<vector<int>>& edges){
    int n = edges.size();
    LowLink ll(edges);
    vector<vector<int>> not_bridge_graph(n);
    for(int i = 0; i < n; ++i)
        for(auto j : edges[i]){
            pair<int,int> min_max = minmax(i, j);
            auto iter = lower_bound(ll.bridge.begin(), ll.bridge.end(), min_max);
            if(iter == ll.bridge.end() || *iter != min_max)
                not_bridge_graph[i].push_back(j);
        }

    vector<int> group(n, -1);
    function<void(int)> group_dfs = [&](int x){
        for(auto y : not_bridge_graph[x])
            if(group[y] == -1){
                group[y] = group[x];
                group_dfs(y);
            }
    };
    int group_cnt = 0;
    for(int i = 0; i < n; ++i)
        if(group[i] == -1){
            group[i] = group_cnt++;
            group_dfs(i);
        }
    vector<vector<int>> group_elm_list(group_cnt);
    for(int i = 0; i < n; ++i)
        group_elm_list[group[i]].push_back(i);

    vector<vector<pair<int,int>>> same_group_edges(group_cnt);
    vector<vector<int>> tree_edges(group_cnt);
    vector<int> par(group_cnt, -1);
    vector<vector<int>> childs(group_cnt);

    for(int i = 0; i < n; ++i)
        for(auto j : edges[i])
            if(group[i] == group[j] && i < j)
                same_group_edges[group[i]].emplace_back(i, j);

    for(auto& p : ll.bridge){
        tree_edges[group[p.first]].push_back(group[p.second]);
        tree_edges[group[p.second]].push_back(group[p.first]);
    }
    vector<bool> flag(n, false);
    function<void(int)> tree_dfs = [&](int x){
        for(auto y : tree_edges[x])
            if(!flag[y]){
                flag[y] = true;
                par[y] = x;
                childs[x].push_back(y);
                tree_dfs(y);
            }
    };
    flag[0] = true;
    tree_dfs(0);

    Result res;
    res.group_cnt = group_cnt;
    res.group_elm_list = move(group_elm_list);
    res.same_group_edges = move(same_group_edges);
    res.bridges = move(ll.bridge);
    res.arts = move(ll.art);
    res.group = move(group);
    res.tree_graph = move(tree_edges);
    res.par = move(par);
    res.childs = move(childs);
    return res;
}

#line 18 "verify/lowlink_tree.test.cpp"

signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<int> u(m), v(m);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    vector<vector<int>> edges(n);
    for(int i = 0; i < m; ++i){
        cin >> u[i] >> v[i];
        --u[i], --v[i];
        edges[u[i]].push_back(v[i]);
        edges[v[i]].push_back(u[i]);
    }
    auto res = two_edge_connected_components_tree(edges);
    int k = res.group_cnt;
    vector<int> values(k, 0);
    for(int i = 0; i < n; ++i)
        values[res.group[i]] += a[i];

    auto& par = res.par;
    auto& childs = res.childs;
    vector<int> dp(k, 0);
    vector<unordered_map<int, int>> dp2(k);
    function<void(int)> f = [&](int x){
        int val = 0;
        for(auto y : childs[x]){
            f(y);
            chmax(val, dp[y]);
        }
        dp[x] = values[x] + val;
    };
    f(0);

    int ans = 0;
    function<void(int)> g = [&](int x){
        multiset<int> v{0, 0};
        for(auto y : childs[x]){
            v.insert(dp[y]);
            v.erase(v.begin());
            g(y);
        }
        chmax(ans, values[x] + *prev(v.end()) + *prev(v.end(), 2));
    };
    g(0);
    cout << ans << endl;

    return 0;
}
Back to top page