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

• 問題: No.922 東北きりきざむたん
• ユーザー: GOTKAKO
• 提出日時: 2026-09-16 04:18:13
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 102 ms / 2,000 ms
• コード長: 7,729 bytes
• コンパイル時間: 2,189 ms
• コンパイル使用メモリ: 244,880 KB
• 実行使用メモリ: 72,156 KB
• 最終ジャッジ日時: 2026-09-16 04:18:21
• 合計ジャッジ時間: 7,155 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

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

ソースコード

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

struct HLD1{
    //1.頂点のみパターン.
    int n = 0,tim = 0;
    vector<int> dist,in,out,siz,head,par,ord;
    HLD1(vector<vector<int>> &Graph,int Root = 0):n(Graph.size()),dist(n),in(n),out(n),siz(n),head(n),par(n),ord(n){
        iota(head.begin(),head.end(),0);
        auto dfs1 = [&](auto dfs1,int pos,int back,int d) -> int {
            par.at(pos) = back,dist.at(pos) = d;
            int maxsiz = 0,big = -1,idx = -1,ret = 1;
            for(auto to : Graph.at(pos)){
                idx++;
                if(to == back) continue;
                int kid = dfs1(dfs1,to,pos,d+1);
                ret += kid;
                if(maxsiz < kid) maxsiz = kid,big = idx;
            }
            if(big > -1) swap(Graph.at(pos).at(0),Graph.at(pos).at(big));
            return siz.at(pos) = ret;
        };
        int time = 0;
        auto dfs2 = [&](auto dfs2,int pos,int back) -> void {
            ord.at(time) = pos,in.at(pos) = time++;
            if(Graph.at(pos).size() > 1) head.at(Graph.at(pos).at(0)) = head.at(pos);
            for(auto to : Graph.at(pos)) if(to != back) dfs2(dfs2,to,pos);
            out.at(pos) = time;
        };
        dfs1(dfs1,Root,-1,0),dfs2(dfs2,Root,-1);
    } 
    vector<pair<int,int>> findpath(int u,int v){ //O(logN).
    //dfs行きがけ順に並べた頂点のセグ木の区間を返す.
    //行きがけ順はrep(0-n)give[in[i]]=A[i].
    //交換法則が成り立たない時は修正必須.
        vector<pair<int,int>> ret;
        while(head.at(u) != head.at(v)){
            if(dist.at(head.at(u)) > dist.at(head.at(v))) swap(u,v);
            ret.push_back({in.at(head.at(v)),in.at(v)+1});
            v = par.at(head.at(v));
        }
        if(in.at(u) > in.at(v)) swap(u,v);
        ret.push_back({in.at(u),in.at(v)+1});
        return ret;
    }
    pair<int,int> subtree(int u){return {in.at(u),out.at(u)};}
    int lca(int u,int v){ //O(logN).
        int hu = head.at(u),hv = head.at(v);
        while(hu != hv){
            if(dist.at(hu) < dist.at(hv)) v = par.at(hv),hv = head.at(v);
            else u = par.at(hu),hu = head.at(u); 
        }
        if(dist.at(u) <= dist.at(v)) return u;
        else return v;
    }
    int jump(int u,int v,int k){ //u->vパスでuからk個進んだ頂点 O(logN).
        int l = lca(u,v);
        if(k <= dist.at(u)-dist.at(l)) return la(u,k);
        k -= dist.at(u)-dist.at(l);
        if(k <= dist.at(v)-dist.at(l)) return la(v,dist.at(v)-dist.at(l)-k);
        return -1; //パス長<kなら-1.
    }
    int la(int u,int k){ //uからk個根に戻った時. O(logN).
        int hu = head.at(u);
        while(u != -1 && dist.at(u)-dist.at(hu) < k){
            k -= dist.at(u)-dist.at(hu)+1;
            u = par.at(hu);
            if(u != -1) hu = head.at(u);
        }
        if(u == -1) return -1;
        return ord.at(in.at(u)-k);
    }
    int distance(int u,int v){return dist.at(u)+dist.at(v)-2*dist.at(lca(u,v));}
};

template<typename T> 
class Cumulative{ //1次元.
    private:
    T op(T a,T b){return {a.first+b.first,a.second+b.second};}
    T inv(T a){return {0,0};} //ない場合はスルー->rangeans使用不可.
    T e(){return {0,0};}
    int n;
    vector<T> L,R;
    public:
    Cumulative(){}
    Cumulative(vector<T> &A){make(A);}
    void make(vector<T> &A){
        L = A,R = A;
        n = A.size();
        for(int i=1; i<n; i++) L.at(i) = op(L.at(i-1),L.at(i));
        for(int i=n-2; i>=0; i--) R.at(i) = op(R.at(i),R.at(i+1));
    }
    T rangeans(int l,int r){ //[l,r]だよL<0も許容 逆元はいる.
        if(l > r || r < 0) return e();
        T ret = L.at(r);
        if(l > 0) ret = op(ret,inv(L.at(l-1)));
        return ret;
    }
    T skipone(int pos){ //0<=pos<n;
        T ret = e();
        if(pos > 0) ret = L.at(pos-1);
        if(pos != n-1) ret = op(ret,R.at(pos+1));
        return ret;
    }
    T skiprange(int l,int r){//l<=r.
        T ret = e();
        if(l > 0) ret = L.at(l-1);
        if(r != n-1) ret = op(ret,R.at(r+1));
        return ret;
    }
    T get(int pos){return L.at(pos);}
    vector<T> allA(){return L;}
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto f = [&](vector<vector<int>> Graph,vector<int> C,vector<pair<int,int>> AB) -> long long {
        int N = Graph.size();
        if(N == 1) return 0;
        HLD1 H(Graph);
        long long ret = 1e18;
        vector<int> par(N,-1);
        vector<vector<pair<long long,long long>>> kid(N);
        {
            auto dfs = [&](auto dfs,int pos,int back) -> pair<long long,long long> {
                int n = Graph.at(pos).size();
                kid.at(pos).resize(n);
                long long ret1 = C.at(pos),ret2 = 0;
                for(int i=0; i<n; i++){
                    int to = Graph.at(pos).at(i);
                    if(to == back) par.at(pos) = i;
                    else{
                        auto [k1,k2] = dfs(dfs,to,pos);
                        kid.at(pos).at(i) = {k1,k2};
                        ret1 += k1,ret2 += k2;
                    }
                }
                return {ret1,ret1+ret2};
            };
            dfs(dfs,0,-1);
        }
        {
            auto dfs = [&](auto dfs,int pos,int back,pair<long long,long long> take) -> void {
                if(back != -1) kid.at(pos).at(par.at(pos)) = take;
                Cumulative Z(kid.at(pos));
                int n = Graph.at(pos).size();
                ret = min(ret,Z.get(n-1).second);
                for(int i=0; i<n; i++){
                    int to = Graph.at(pos).at(i);
                    if(to == back) continue;
                    auto [v1,v2] = Z.skipone(i);
                    v1 += C.at(pos),v2 += v1;
                    dfs(dfs,to,pos,{v1,v2});
                }
            };
            dfs(dfs,0,-1,{0,0});
        }
        for(auto [a,b] : AB) ret += H.distance(a,b);
        return ret;
    };
    {
        int N,M,q; cin >> N >> M >> q;
        vector<vector<int>> Graph(N);
        for(int i=0; i<M; i++){
            int u,v; cin >> u >> v;
            u--; v--;
            Graph.at(u).push_back(v);
            Graph.at(v).push_back(u);
        }
        vector<vector<int>> Ps;
        vector<int> belong(N,-1);
        queue<int> Q;
        for(int i=0; i<N; i++) if(belong.at(i) == -1){
            belong.at(i) = Ps.size(),Q.push(i);
            vector<int> P;
            while(Q.size()){
                int pos = Q.front(); Q.pop();
                P.push_back(pos);
                for(auto to : Graph.at(pos)) if(belong.at(to) == -1) belong.at(to) = belong.at(i),Q.push(to);
            }
            Ps.push_back(P);
        }
        vector<vector<int>> Query(N);
        while(q--){
            int a,b; cin >> a >> b,a--,b--;
            Query.at(a).push_back(b);
            Query.at(b).push_back(a);
        }
        long long answer = 0;
        vector<int> Pos(N,-1);
        for(auto &P : Ps){
            int n = P.size();
            vector<int> C(n);
            vector<pair<int,int>> AB;
            vector<vector<int>> G(n);
            for(int i=0; i<n; i++) Pos.at(P.at(i)) = i;
            for(auto pos : P){
                for(auto to : Graph.at(pos)) G.at(Pos.at(pos)).push_back(Pos.at(to));
                for(auto to : Query.at(pos)){
                    if(Pos.at(to) != -1){
                        if(Pos.at(pos) < Pos.at(to)) AB.push_back({Pos.at(pos),Pos.at(to)});
                    }
                    else C.at(Pos.at(pos))++;
                }
            }
            answer += f(G,C,AB);
            for(int i=0; i<n; i++) Pos.at(P.at(i)) = -1;
        }
        cout << answer << endl;
    }


}