結果

問題 No.399 動的な領主
ユーザー TAISA_TAISA_
提出日時 2019-02-23 18:35:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 175 ms / 2,000 ms
コード長 2,781 bytes
コンパイル時間 2,033 ms
コンパイル使用メモリ 179,036 KB
実行使用メモリ 16,640 KB
最終ジャッジ日時 2024-11-30 22:34:20
合計ジャッジ時間 5,716 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<30;
const ll LINF=1LL<<62;
const double eps=1e-9;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type fill_v(T& t,const V& v){t=v;}
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type fill_v(T& t,const V& v){for(auto &e:t)fill_v(e,v);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct HLDecomposition{
    int n,pos;
    vector<vector<int>> G;
    vector<ll> sum;
    vector<int> nid,fst,hv,id,siz,dep,par;
    HLDecomposition(int n_):n(n_),pos(0),G(n),sum(n+10),nid(n,-1),fst(n,-1),hv(n,-1),id(n),siz(n,1),par(n,-1){}
    void add_edge(int u,int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }
    void build(int rt){
        par[rt]=-1;
        dfs(rt);
        bfs(rt);
    }
    void dfs(int v){
        int ma=0;
        for(auto u:G[v]){
            if(u==par[v])continue;
            par[u]=v;
            dfs(u);
            siz[v]+=siz[u];
            if(ma<siz[u]){
                ma=siz[u];
                hv[v]=u;
            }
        }
    }
    void bfs(int rt){
        queue<int> q;
        q.push(rt);
        while(!q.empty()){
            int h=q.front();q.pop();
            for(int i=h;i!=-1;i=hv[i]){
                nid[i]=pos++;
                id[nid[i]]=i;
                fst[i]=h;
                for(auto j:G[i]){
                    if(j!=par[i]&&j!=hv[i]){
                        q.push(j);
                    }
                }
            }
        }
    }
    void query(int u,int v){
        while(1){
            if(nid[u]>nid[v])swap(u,v);
            sum[max(nid[fst[v]],nid[u])]++;
            sum[nid[v]+1]--;
            if(fst[v]!=fst[u]){
                v=par[fst[v]];
            }else{
                break;
            }
        }
    }
    ll ans(){
        for(int i=1;i<=n;i++){
            sum[i]+=sum[i-1];
        }
        ll res=0;
        for(int i=0;i<n;i++){
            res+=(1LL+sum[i])*sum[i]/2;
        }
        return res;
    }
};
int main(){
    int n;cin>>n;
    HLDecomposition tree(n);
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;--u;--v;
        tree.add_edge(u,v);
    }
    tree.build(0);
    int q;cin>>q;
    while(q--){
        int u,v;cin>>u>>v;--u;--v;
        tree.query(u,v);
    }
    cout<<tree.ans()<<endl;
}
0