#396897 (C++14) No.922 東北きりきざむたん

• 問題: No.922 東北きりきざむたん
• ユーザー: toma
• 提出日時: 2019-11-08 23:28:46
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 332 ms / 2,000 ms
• コード長: 6,957 bytes
• コンパイル時間: 2,754 ms
• コンパイル使用メモリ: 210,832 KB
• 実行使用メモリ: 33,364 KB
• 最終ジャッジ日時: 2024-09-15 02:35:28
• 合計ジャッジ時間: 8,322 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 4
other	AC * 26

ソースコード

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;


class UnionFind {
public:
    vector<int>rank, parent;
    //初期化
    UnionFind(int size) {
        rank.resize(size, 0);
        parent.resize(size, 0);
        rep(i, size)parent[i] = i;
    }
    //木の根を求める
    int find(int x) {
        if (parent[x] == x)return x;
        else return parent[x] = find(parent[x]);
    }
    //xとyの属する集合を併合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)return;
        if (rank[x] < rank[y])
            parent[x] = y;
        else {
            parent[y] = x;
            if (rank[x] == rank[y])rank[x]++;
        }
    }
    //xとyが同じ集合に属するか否か
    bool same(int x, int y) {
        return (find(x) == find(y));
    }
};



vector<vector<int>> edges;
vector<int> weight;
vector<pair<int, int>> sizeSubtree; // {コスト和, 頂点の数}
UnionFind uf(0);

map<int, int> tot;
map<int, int>cent;

void SubFindCentroids(int v, int parent_of_v = -1) {
    const int N = tot[uf.find(v)];
    sizeSubtree[v] = { 0,weight[v] };

    for (auto ch : edges[v]) {
        if (ch == parent_of_v) continue;
        SubFindCentroids(ch, v);
        auto res = sizeSubtree[ch];
        res.first += res.second;
        sizeSubtree[v].first += res.first;
        sizeSubtree[v].second += res.second;
    }
}

int findCent(int now) {
    int cost, cnt;
    tie(cost, cnt) = sizeSubtree[now];
    int w = weight[now];

    int bcost = cost;
    int bpos = now;
    for (int next : edges[now]) {
        int ncost, ncnt;
        tie(ncost, ncnt) = sizeSubtree[next];
        ncost = (cost - ncnt) + (cnt - ncnt);
        if (ncost < bcost) {
            bcost = ncost;
            bpos = next;
        }
    }
    if (now == bpos)return now;
    int ncost, ncnt;
    tie(ncost, ncnt) = sizeSubtree[bpos];
    sizeSubtree[now] = { cost - ncost - ncnt,cnt - ncnt };
    sizeSubtree[bpos] = { bcost, tot[uf.find(now)] };
    return findCent(bpos);
}


using Graph = vector<vector<int>>;
struct HLDecomposition {
    using pii = pair<int, int>;
    int n;
    Graph G;
    vector<int> vid, inv, par, depth, subsize, head, prev, next, type;

    HLDecomposition(const Graph& G_) :
        n(G_.size()), G(G_),
        vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1),
        head(n), prev(n, -1), next(n, -1), type(n) {}
    void build(vector<int> roots = { 0 }) {
        int curtype = 0, pos = 0;
        for (int root : roots) {
            decide_heavy_edge(root);
            reconstruct(root, curtype++, pos);
        }
    }
    void decide_heavy_edge(int root) {
        stack<pii> st;
        par[root] = -1, depth[root] = 0;
        st.emplace(root, 0);
        while (!st.empty()) {
            int now = st.top().first;
            int& way = st.top().second;
            if (way < G[now].size()) {
                int child = G[now][way++];
                if (child == par[now])continue;
                par[child] = now;
                depth[child] = depth[now] + 1;
                st.emplace(child, 0);
            }
            else {
                st.pop();
                int maxsize = 0;
                for (auto child : G[now]) {
                    if (child == par[now])continue;
                    subsize[now] += subsize[child];
                    if (maxsize < subsize[child]) {
                        maxsize = subsize[child];
                        prev[child] = now;
                        next[now] = child;
                    }
                }
            }
        }
    }
    void reconstruct(int root, int curtype, int& pos) {
        stack<int> st({ root });
        while (!st.empty()) {
            int start = st.top(); st.pop();
            for (int v = start; v != -1; v = next[v]) {
                type[v] = curtype;
                vid[v] = pos++;
                inv[vid[v]] = v;
                head[v] = start;
                for (auto child : G[v]) {
                    if (child != par[v] && child != next[v]) {
                        st.push(child);
                    }
                }
            }
        }
    }

    // node query [u, v], f([left, right])
    void foreach_nodes(int u, int v, const function<void(int, int)>& f) {
        while (true) {
            if (vid[u] > vid[v])swap(u, v);
            f(max(vid[head[v]], vid[u]), vid[v]);
            if (head[u] != head[v])v = par[head[v]];
            else break;
        }
    }

    // edge query[u,v] f([left, right])
    // seg_node[vid[i]] := edge(par[i] -> i)
    void foreach_edges(int u, int v, const function<void(int, int)>& f) {
        while (true) {
            if (vid[u] > vid[v])swap(u, v);
            if (head[u] != head[v]) {
                f(vid[head[v]], vid[v]);
                v = par[head[v]];
            }
            else {
                if (u != v)f(vid[u] + 1, vid[v]);
                break;
            }
        }
    }
    int lca(int u, int v) {
        while (true) {
            if (vid[u] > vid[v])swap(u, v);
            if (head[u] == head[v])return u;
            v = par[head[v]];
        }
    }
};


int main()
{
    int N, M, Q;
    cin >> N >> M >> Q;
    edges.resize(N);
    weight.resize(N);
    uf = UnionFind(N);

    sizeSubtree.resize(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
        uf.unite(u, v);
    }

    vector<pair<int, int>> ab;
    rep(i, Q) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        ab.push_back({ a,b });
        if (!uf.same(a, b)) {
            weight[a]++;
            weight[b]++;
            tot[uf.find(a)]++;
            tot[uf.find(b)]++;
        }
    }

    {
        set<int> st;
        rep(i, N) {
            int par = uf.find(i);
            if (st.find(par) != st.end())continue;
            st.insert(par);
            SubFindCentroids(i);
            cent[par] = findCent(i);
        }
    }

    HLDecomposition hld(edges);
    {
        set<int> st;
        rep(i, N)st.insert(uf.find(i));
        vector<int> routes;
        for (int num : st)routes.push_back(num);
        hld.build(routes);
    }

    ll res = 0;
    for (auto route : ab) {
        int a, b;
        tie(a, b) = route;
        if (uf.same(a, b)) {
            int m = hld.lca(a, b);
            res += hld.depth[a] + hld.depth[b] - 2 * hld.depth[m];
        }
        else {
            int from = cent[uf.find(a)];
            assert(uf.same(a, from));
            int m = hld.lca(a, from);
            res += hld.depth[a] + hld.depth[from] - 2 * hld.depth[m];

            int to = cent[uf.find(b)];
            m = hld.lca(b, to);
            res += hld.depth[b] + hld.depth[to] - 2 * hld.depth[m];
        }
    }
    cout << res << endl;
    return 0;
}