#1120846 (C++17) No.3272 Separate Contractions

• 問題: No.3272 Separate Contractions
• ユーザー: GOTKAKO
• 提出日時: 2025-09-12 22:47:03
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 856 ms / 3,000 ms
• コード長: 11,815 bytes
• コンパイル時間: 3,203 ms
• コンパイル使用メモリ: 229,248 KB
• 実行使用メモリ: 114,708 KB
• 最終ジャッジ日時: 2025-09-12 23:43:21
• 合計ジャッジ時間: 26,572 ms
• ジャッジサーバーID （参考情報）: judge1 / judge6

ファイルパターン	結果
sample	AC * 3
other	AC * 43

ソースコード

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

struct HLD2{
    //2.辺のみパターン.
    int n = 0,tim = 0;
    vector<int> dist,in,out,siz,head,pre,par;
    vector<long long> connect;
    vector<long long> make(vector<vector<pair<int,long long>>> &Graph){
        n = Graph.size();
        dist.resize(n),in.resize(n),siz.resize(n,1),out.resize(n);
        head.resize(n),par.resize(n),connect.resize(n);
        auto dfs1 = [&](auto dfs1,int pos,int back = -1,int d = 0) -> void {
            par.at(pos) = back; dist.at(pos) = d;
            if(Graph.at(pos).size() && Graph.at(pos).at(0).first == back) swap(Graph.at(pos).at(0),Graph.at(pos).back());
            for(auto &to : Graph.at(pos)){
                if(to.first == back) continue;
                dfs1(dfs1,to.first,pos,d+1);
                siz.at(pos) += siz.at(to.first);
                if(siz.at(Graph.at(pos).at(0).first) < siz.at(to.first)) swap(Graph.at(pos).at(0),to); 
            }
        };
        vector<long long> ret(n);
        auto dfs2 = [&](auto dfs2,int pos,int back = -1) -> void {
            in.at(pos) = tim++;
            for(auto &[to,w] : Graph.at(pos)){
                if(to == back) continue;
                if(to == Graph.at(pos).at(0).first) head.at(to) = head.at(pos),ret.at(tim-1) = w;
                else head.at(to) = to,connect.at(to) = w; //頂点との変更点1.
                dfs2(dfs2,to,pos);
            }
            out.at(pos) = tim;
        };
        dfs1(dfs1,0); dfs2(dfs2,0);
        return ret;
    }

    vector<pair<int,int>> findpath(int u,int v){
        //dfs行きがけ順に並べた頂点のセグ木の区間を返す.
        //R = -1はconnect[L]の値.
        //行きがけ順は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);
            if(head.at(v) != v) ret.push_back({in.at(head.at(v)),in.at(v)});
            ret.push_back({head.at(v),-1});
            v = par.at(head.at(v));
        }
        if(in.at(u) > in.at(v)) swap(u,v);
        if(u != v) ret.push_back({in.at(u),in.at(v)});
        return ret;
    }
};

using SS = long long;
using FF = long long;
class LazySegmentTree{
    //ACL超参考にしてる というかパクリ.
    //verify十分だけど注意.
    private:
    vector<SS> dat;
    vector<FF> lazy;
    public:
    int siz = -1,n = -1,log = 0;
 
    SS op(SS a,SS b){return a+b;}
    SS mapping(FF f, SS x){return f+x;}
    FF composition(FF f, FF g){return f+g;}
    SS e(){return 0;}
    FF id(){return 0;}
    //op区間演算 mapping lazy→data composition lazy→lazy
    //e 単位元 id map(id,a)=a
 
    LazySegmentTree(int N){init(N);}
    LazySegmentTree(const vector<SS> &A){//配列サイズに合わせる.
        siz = 1; n = A.size(); log = 0;
        while(siz < n) siz <<= 1,log++;
        dat.resize(siz*2,e());
        lazy.resize(siz,id());
        for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
        for(int i=siz-1; i>0; i--) merge(i);
    }
    void init(int N){ //単位元になる.
        siz = 1; n = N; log = 0;
        while(siz < n) siz *= 2,log++;
        dat.assign(siz*2,e());
        lazy.assign(siz,id());
    }
    void init(const vector<SS> &A){ //配列サイズに合わせる.
        siz = 1; n = A.size(); log = 0;
        while(siz < n) siz <<= 1,log++;
        dat.resize(siz*2,e());
        lazy.assign(siz,id());
        for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
        for(int i=siz-1; i>0; i--) merge(i);
    }
 
    private:
    void eval(int u,FF f){
        //u番目にfを適用したあと保留.
        if(u == 0) return;
        dat.at(u) = mapping(f,dat.at(u));
        if(u < siz) lazy.at(u) = composition(f,lazy.at(u));
    }
    void spread(int u){ //uにあるFF保留を伝播.
        if(u == 0 || id() == lazy.at(u)) return;
        eval(2*u,lazy.at(u));
        eval(2*u+1,lazy.at(u));
        lazy.at(u) = id();
    }
    void merge(int u){dat.at(u) = op(dat.at(u*2),dat.at(u*2+1));} //子2つからマージ.
    public:
    void set(int pos,SS x){ //1点変更.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        dat.at(pos) = x;
        while(pos > 1) pos >>= 1,merge(pos); 
    }
    void update(int pos,FF f){ //1点更新 変数抜かして区間更新になってないか注意!.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        dat.at(pos) = mapping(f,dat.at(pos));
        while(pos > 1) pos >>= 1,merge(pos);
    }
    void update(int l,int r,FF f){ //区間更新.
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return;
        l += siz; r += siz;
        for(int i=log; i>0; i--){
            if(((l>>i)<<i) != l) spread(l>>i);
            if(((r>>i)<<i) != r) spread((r-1)>>i); 
        }
        int memoL = l,memoR = r;
        while(l < r){
            if(l&1) eval(l++,f);
            if(r&1) eval(--r,f);
            l >>= 1; r >>= 1;
        }
        l = memoL,r = memoR;
        while((l&1) == 0) l >>= 1;
        while((r&1) == 0) r >>= 1;
        r--; //-1注意.
        while(l > 1) l >>= 1,merge(l);
        while(r > 1) r >>= 1,merge(r); 
    }
 
    SS get(int pos){ //1点取得.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        return dat.at(pos);
    }
    SS rangeans(int l,int r){ //区間取得.
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return e();
        l += siz; r += siz;
        for(int i=log; i>0; i--){
            if(((l>>i)<<i) != l) spread(l>>i);
            if(((r>>i)<<i) != r) spread((r-1)>>i); 
        }
 
        SS retl = e(),retr = e();
        while(l < r){
            if(l&1) retl = op(retl,dat.at(l++));
            if(r&1) retr = op(dat.at(--r),retr);
            l >>= 1; r >>= 1;
        }
        return op(retl,retr);
    }
    SS allrange(){return dat.at(1);} //全体取得.
 
    int maxright(const function<bool(SS)> f,int l = 0){
        assert(0 <= l && l <= n && f(e()));
        if(l == n) return n;
        l += siz;
        for(int i=log; i>0; i--) spread(l>>i);
        SS now = e();
        do{
            while(l%2 == 0) l >>= 1;
            SS next = op(now,dat.at(l));
            if(f(next) == false){
                while(l < siz){
                    spread(l); l <<= 1;
                    next = op(now,dat.at(l));
                    if(f(next)) now = next,l++;
                }
                return l-siz;
            }
            now = next; l++;
        }while((l&-l) != l);
        return n;
    }
    int minleft(const function<bool(SS)> f,int r = -1){
        if(r == -1) r = n;
        assert(0 <= r && r <= n && f(e()));
        if(r == 0) return 0;
        r += siz;
        for(int i=log; i>0; i--) spread((r-1)>>i);
        SS now = e();
        do{
            r--;
            while(r&1) r >>= 1;
            if(r == 0) r = 1;
            SS next = op(dat.at(r),now);
            if(f(next) == false){
                while(r < siz){
                    spread(r);
                    r <<= 1; r++;
                    next = op(now,dat.at(r));
                    if(f(next)) now = next,r--;
                }
                return r+1-siz;
            }
            now = next;
        }while((r&-r) != r);
        return 0;
    }
};

template<typename T> 
class Cumulative{ //1次元.
    private:
    T op(T a,T b){
        auto [a1,a2,da] = a;
        auto [b1,b2,db] = b;
        if(a1 == b1) return {a1,b1,-2};
        if(a2 >= b1) return a;
        if(b2 >= a2) return b;
        if(a1 > b1) return {a1,b1,da};
        return {b1,a1,db};
    }
    T inv(T a){return a;} //ない場合はスルー->rangeans使用不可.
    T e(){return {0,0,-2};}
    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);

    int N; cin >> N;
    vector<vector<pair<int,long long>>> Graph(N);
    for(int i=0; i<N-1; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back({v,i});
        Graph.at(v).push_back({u,i});
    }

    HLD2 H; H.make(Graph);
    LazySegmentTree Z(N);
    vector<int> minus(N);
    long long sum = 0;
    
    using T = tuple<int,int,int>;
    vector<int> par(N,-1);
    vector<vector<T>> kid(N);
    {
        auto dfs = [&](auto dfs,int pos,int back) -> T { 
            int ret1 = 0,ret2 = 0,ret3 = pos;
            int n = Graph.at(pos).size();
            kid.at(pos).resize(n);
            for(int i=0; i<n; i++){
                int to = Graph.at(pos).at(i).first;
                if(to == back){par.at(pos) = i; continue;}
                auto [one,two,down] = dfs(dfs,to,pos);
                kid.at(pos).at(i) = {one,two,down};
                if(ret1 == one) ret1 = one,ret2 = one,ret3 = pos;
                else if(two >= ret1) ret1 = one,ret2 = two,ret3 = down;
                else if(ret2 >= one){}
                else{
                    if(ret1 > one) ret2 = one;
                    else ret2 = ret1,ret1 = one,ret3 = down;
                }
            }
            ret1++,ret2++;
            return {ret1,ret2,ret3};
        };
        dfs(dfs,0,-1);
    }
    vector<long long> answer(N-1);
    {
        auto dfs = [&](auto dfs,int pos,int back,T take,int epos = -1) -> void {
            if(back != -1) kid.at(pos).at(par.at(pos)) = take;
            Cumulative C(kid.at(pos));
            int n = Graph.at(pos).size();
            auto [one,two,down] = C.get(n-1);
            sum += one;
            if(down == -2) down = pos;
            if(down != pos){
                for(auto [l,r] : H.findpath(pos,down)){
                    if(r == -1) minus.at(l)++;
                    else Z.update(l,r,1); 
                }
            }
            if(epos != -1){
                int t1 = H.in.at(pos),t2 = H.out.at(pos),t3 = H.in.at(down);
                if(t1 <= t3 && t3 < t2) answer.at(epos) -= one;
                else answer.at(epos) -= one-1; 
            }
            for(int i=0; i<n; i++){
                int to = Graph.at(pos).at(i).first; epos = Graph.at(pos).at(i).second;
                if(to == back) continue;
                tie(one,two,down) = C.skipone(i);
                one++,two++;
                if(down == -2) down = pos;
                dfs(dfs,to,pos,{one,two,down},epos);
            }
        };
        dfs(dfs,0,-1,{0,0,0});
    }
    for(int i=0; i<N; i++){
        for(auto [to,epos] : Graph.at(i)){
            if(i > to) continue;
            for(auto [l,r] : H.findpath(i,to)){
                if(r == -1) answer.at(epos) -= minus.at(l);
                else answer.at(epos) -= Z.get(l);
            }
        }
    }
    for(auto a : answer) cout << a+sum << "\n";
}