結果

問題 No.399 動的な領主
コンテスト
ユーザー nxteru
提出日時 2018-03-28 08:54:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 976 ms / 2,000 ms
コード長 2,295 bytes
コンパイル時間 805 ms
コンパイル使用メモリ 73,760 KB
実行使用メモリ 27,416 KB
最終ジャッジ日時 2024-06-25 13:02:55
合計ジャッジ時間 9,773 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long ll;
int n,k,q,sz[100005],hv[100005],id[100005],hd[100005],cn[100005],vs[100005],dp[100005];
vector<int>g[100005];
ll seg[1<<19],la[1<<19],ans;
void dfs1(int v,int p){
    sz[v]=1;
    hv[v]=-1;
    for(int i=0;i<g[v].size();i++){
        if(g[v][i]!=p){
            dfs1(g[v][i],v);
            sz[v]+=sz[g[v][i]];
            if(hv[v]==-1||sz[g[v][i]]>sz[hv[v]])hv[v]=g[v][i];
        }
    }
}
void dfs2(int v,int p,int  d,int h){
    hd[k]=h;
    cn[k]=cn[h];
    dp[k]=d;
    id[v]=k;
    vs[k++]=v;
    if(hv[v]!=-1){
        dfs2(hv[v],v,d+1,h);
    }
    for(int i=0;i<g[v].size();i++){
        if(g[v][i]!=p&&g[v][i]!=hv[v]){
            cn[k]=id[v];
            dfs2(g[v][i],v,d+1,k);
        }
    }
}
void lazy(int r,int l,int o){
    seg[o]+=(l-r+1)*la[o];
    if(l-r>0){
        la[o*2+1]+=la[o];
        la[o*2+2]+=la[o];
    }
    la[o]=0;
}
void add(int a,int b,int r,int l,int o,ll x){
    lazy(r,l,o);
    if(l<a||b<r)return;
    if(a<=r&&l<=b){
        la[o]+=x;
        lazy(r,l,o);
        return;
    }
    add(a,b,r,(r+l-1)/2,o*2+1,x);
    add(a,b,(r+l+1)/2,l,o*2+2,x);
    seg[o]=seg[o*2+1]+seg[o*2+2];
}
ll sum(int a,int b,int r,int l,int o){
    lazy(r,l,o);
    if(l<a||b<r)return ll(0);
    if(a<=r&&l<=b)return seg[o];
    return sum(a,b,r,(r+l-1)/2,o*2+1)+sum(a,b,(r+l+1)/2,l,o*2+2);
}
int main(void){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        g[--a].push_back(--b);
        g[b].push_back(a);
    }
    for(int i=0;i<n;i++)add(i,i,0,(1<<18)-1,0,1);
    dfs1(0,-1);
    dfs2(0,-1,0,0);
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        a=id[a-1];b=id[b-1];
        while(hd[a]!=hd[b]){
            if(dp[hd[a]]<dp[hd[b]]){
                ans+=sum(hd[b],b,0,(1<<18)-1,0);
                add(hd[b],b,0,(1<<18)-1,0,1);
                b=cn[b];
            }else{
                ans+=sum(hd[a],a,0,(1<<18)-1,0);
                add(hd[a],a,0,(1<<18)-1,0,1);
                a=cn[a];
            }
        }
        ans+=sum(min(a,b),max(a,b),0,(1<<18)-1,0);
        add(min(a,b),max(a,b),0,(1<<18)-1,0,1);
    }
    printf("%lld\n",ans);
}
0