結果

問題 No.399 動的な領主
ユーザー nxterunxteru
提出日時 2018-03-28 08:54:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 801 ms / 2,000 ms
コード長 2,295 bytes
コンパイル時間 748 ms
コンパイル使用メモリ 72,800 KB
実行使用メモリ 26,480 KB
最終ジャッジ日時 2023-09-07 19:17:27
合計ジャッジ時間 8,398 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
14,032 KB
testcase_01 AC 4 ms
13,756 KB
testcase_02 AC 4 ms
13,768 KB
testcase_03 AC 4 ms
13,780 KB
testcase_04 AC 8 ms
13,936 KB
testcase_05 AC 55 ms
14,356 KB
testcase_06 AC 772 ms
18,864 KB
testcase_07 AC 753 ms
18,792 KB
testcase_08 AC 759 ms
18,772 KB
testcase_09 AC 776 ms
18,764 KB
testcase_10 AC 11 ms
13,808 KB
testcase_11 AC 45 ms
14,340 KB
testcase_12 AC 581 ms
19,244 KB
testcase_13 AC 562 ms
19,196 KB
testcase_14 AC 134 ms
26,480 KB
testcase_15 AC 212 ms
26,476 KB
testcase_16 AC 327 ms
22,612 KB
testcase_17 AC 801 ms
18,832 KB
testcase_18 AC 773 ms
18,752 KB
権限があれば一括ダウンロードができます

ソースコード

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