結果

問題 No.399 動的な領主
ユーザー mugen_1337mugen_1337
提出日時 2021-04-16 15:47:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,286 ms / 2,000 ms
コード長 8,013 bytes
コンパイル時間 5,106 ms
コンパイル使用メモリ 234,292 KB
実行使用メモリ 34,680 KB
最終ジャッジ日時 2023-09-15 13:01:24
合計ジャッジ時間 14,750 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 6 ms
4,376 KB
testcase_05 AC 77 ms
6,012 KB
testcase_06 AC 1,246 ms
31,044 KB
testcase_07 AC 1,240 ms
29,028 KB
testcase_08 AC 1,201 ms
31,064 KB
testcase_09 AC 1,233 ms
31,116 KB
testcase_10 AC 8 ms
4,380 KB
testcase_11 AC 54 ms
5,740 KB
testcase_12 AC 834 ms
31,220 KB
testcase_13 AC 809 ms
29,056 KB
testcase_14 AC 163 ms
34,680 KB
testcase_15 AC 344 ms
34,608 KB
testcase_16 AC 562 ms
33,328 KB
testcase_17 AC 1,286 ms
31,132 KB
testcase_18 AC 1,260 ms
31,232 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 998244353
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}


// graph template
// ref : https://ei1333.github.io/library/graph/graph-template.cpp
template<typename T=int>
struct Edge{
    int from,to;
    T w;
    int idx;
    Edge()=default;
    Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){}
    operator int() const{return to;}
};

template<typename T=int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int V,E;
    Graph()=default;
    Graph(int n):g(n),V(n),E(0){}

    size_t size(){
        return g.size();
    }
    void resize(int k){
        g.resize(k);
    }
    inline const vector<Edge<T>> &operator[](int k)const{
        return (g.at(k));
    }
    inline vector<Edge<T>> &operator[](int k){
        return (g.at(k));
    }
    void add_directed_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E++);
    }
    void add_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E);
        g[to].emplace_back(to,from,cost,E++);
    }
    void read(int m,int pad=-1,bool weighted=false,bool directed=false){
        for(int i=0;i<m;i++){
            int u,v;cin>>u>>v;
            u+=pad,v+=pad;
            T w=T(1);
            if(weighted) cin>>w;
            if(directed) add_directed_edge(u,v,w);
            else         add_edge(u,v,w);
        }
    }
};


/*
ref : https://ferin-tech.hatenablog.com/entry/2019/11/21/HL%E5%88%86%E8%A7%A3%E3%81%AE%E5%AE%9F%E8%A3%85
      https://ei1333.github.io/library/graph/tree/heavy-light-decomposition.cpp

HLD 
    各頂点から頂点を扱いやすいように並び替えた時の番号への写像を考える
    ! 辺属性で考えたい場合
        頂点iから親方向に伸びている辺をpos[i]にSegment木などにセットし，各メソッドをedge=trueで扱う


    member
        head[i] : iの先頭
        in[i], out[i] : i頂点以下の部分木のin, out

    method
        lca(u, v) : least common ancestor
        dist(u, v) : 距離
        get_path(u, v) : 区間のvectorを返すので各区間でクエリを処理し，mergeすればよい
        get_subtree(u) : 部分木にあたる区間を返す
        pos(u) : 並び替えをした後，頂点uがどの場所へ移るかの射影
*/
template<typename T>
struct HeavyLightDecomposition{
    Graph<T> g;
    vector<int> sz,in,out,head,rev,par;
    vector<T> dis;

    HeavyLightDecomposition(Graph<T> g,int root=0):
    g(g),sz(g.V,0),in(g.V,0),out(g.V,0),head(g.V,0),rev(g.V,0),par(g.V,0),dis(g.V,0){
        dfs1(-1,root);
        int t=0;
        dfs2(-1,root,t);
    }

    void dfs1(int pre,int cur){
        par[cur]=pre;
        sz[cur]=1;
        if(!g[cur].empty() and g[cur][0]==pre) swap(g[cur][0],g[cur].back());
        for(auto &e:g[cur])if(e!=pre){
            dfs1(cur,e);
            sz[cur]+=sz[e];
            dis[e]+=dis[cur]+e.w;
            if(sz[g[cur][0]]<sz[e]) swap(g[cur][0],e);
        }
    }
    void dfs2(int pre,int cur,int &t){
        in[cur]=t++;
        rev[in[cur]]=cur;
        for(auto &e:g[cur])if(e!=pre){
            head[e]=(g[cur][0]==e?head[cur]:e);
            dfs2(cur,e,t);
        }
        out[cur]=t;
    }
    int la(int v,int k){
        for(;;){
            int u=head[v];
            if(in[v]-k>=in[u]) return rev[in[v]-k];
            k-=in[v]-in[u]+1;
            v=par[u];
        }
    }
    int lca(int u,int v){
        for(;;v=par[head[v]]){
            // 深い方から上げていく
            if(in[u]>in[v]) swap(u,v);
            if(head[u]==head[v]) return u;
        }
    }
    T dist(int u,int v){ return dis[u]+dis[v]-dis[lca(u,v)]*2; }

    // return ranges
    vector<pair<int,int>> get_path(int u,int v,bool edge=false){
        vector<pair<int,int>> ret;
        for(;;v=par[head[v]]){
            if(in[u]>in[v]) swap(u,v);
            if(head[u]==head[v]) break;
            ret.emplace_back(in[head[v]],in[v]+1);
        }
        // 最後の区間の始点がLCA
        ret.emplace_back(in[u]+edge,in[v]+1);
        return ret;
    }
    // return one range
    pair<int,int> get_subtree(int u,bool edge=false){
        return {in[u]+edge,out[u]};
    }
    int pos(int u){
        return in[u];
    }
};

template<typename Monoid, typename OperatorMonoid=Monoid>
struct LazySegmentTree{
    using F=function<Monoid(Monoid,Monoid)>;
    using G=function<Monoid(Monoid,OperatorMonoid)>;
    using H=function<OperatorMonoid(OperatorMonoid,OperatorMonoid)>;
 
    private:
 
    int sz,height;
    vector<Monoid> data;
    vector<OperatorMonoid> lazy;
    // propagate lazy value -> data (node k)
    inline void propagate(int k){
        if(lazy[k]!=OM0){
            if(k<sz){
                lazy[2*k+0]=h(lazy[2*k+0],lazy[k]);
                lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
            }
            data[k]=g(data[k],lazy[k]);
            lazy[k]=OM0;
        }
    }
 
    void update(int a,int b,const OperatorMonoid &x,int k,int l,int r){
        propagate(k);
        if(b<=l or r<=a) return ;
        if(a<=l and r<=b){
            lazy[k]=h(lazy[k],x);
            propagate(k);
        }else{
            update(a,b,x,2*k,l,(l+r)/2);
            update(a,b,x,2*k+1,(l+r)/2,r);
            data[k]=f(data[2*k],data[2*k+1]);
        }
    }
 
    Monoid query(int a,int b,int k,int l,int r){
        if(b<=l or r<=a) return M1;
 
        propagate(k);
        if(a<=l and r<=b) return data[k];
 
        Monoid L=query(a,b,2*k+0,l,(l+r)/2);
        Monoid R=query(a,b,2*k+1,(l+r)/2,r);
        return f(L,R);
    }
 
    public:
 
    const F f;
    const G g;
    const H h;
    const Monoid M1;
    const OperatorMonoid OM0;
 
    LazySegmentTree(int n,const F f,const G g,const H h,const Monoid &M1,const OperatorMonoid OM0)
    : f(f),g(g),h(h),M1(M1),OM0(OM0) {
        sz=1;height=0;
        while(sz<n) sz<<=1,height++;
        data.assign(2*sz,M1);lazy.assign(2*sz,OM0);
    }
 
    void set(int k,const Monoid &x){
        data[k+sz]=x;
    }
    void build(){
        for(int k=sz-1;k>0;k--) data[k]=f(data[2*k+0],data[2*k+1]);
    }
    void update(int a,int b,const OperatorMonoid &x){
        update(a,b,x,1,0,sz);
    }
    Monoid query(int a,int b){
        return query(a,b,1,0,sz);
    }
    Monoid operator[](const int &k){
        return query(k,k+1);
    }
}; 
 
using M=pair<ll,ll>;
using OM=ll;
const M M1=M(0,0);
const OM OM0=0;
M segf(M a,M b){
    return M(a.first+b.first,a.second+b.second);
}
M segg(M a,OM b){
    return M(a.first+a.second*b,a.second);
}
ll segh(ll a,ll b){
    return a+b;
}


signed main(){
    int n;cin>>n;
    Graph<int> g(n);
    rep(i,n-1){
        int u,v;cin>>u>>v;u--,v--;
        g.add_edge(u,v);
    }
    HeavyLightDecomposition<int> hld(g);
    LazySegmentTree<M,OM> seg(n,segf,segg,segh,M1,OM0);
    rep(i,n) seg.set(i,{0,1});
    seg.build();

    // rep(i,n){
    //     cout<<i<<" : "<<hld.pos(i)<<endl;
    // }

    int q;cin>>q;
    ll res=0;
    while(q--){
        int u,v;cin>>u>>v;u--,v--;
        for(auto [l,r]:hld.get_path(u,v)){
            seg.update(l,r,1);
            res+=seg.query(l,r).first;
        }
    }
    cout<<res<<endl;
    return 0;
}
0