結果

問題 No.2337 Equidistant
ユーザー momoyuumomoyuu
提出日時 2023-06-02 22:59:24
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,299 ms / 4,000 ms
コード長 3,621 bytes
コンパイル時間 3,761 ms
コンパイル使用メモリ 259,656 KB
実行使用メモリ 77,380 KB
最終ジャッジ日時 2023-08-28 05:23:34
合計ジャッジ時間 28,883 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,380 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 3 ms
4,376 KB
testcase_03 AC 3 ms
4,384 KB
testcase_04 AC 3 ms
4,376 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 9 ms
4,380 KB
testcase_07 AC 9 ms
4,376 KB
testcase_08 AC 9 ms
4,376 KB
testcase_09 AC 9 ms
4,376 KB
testcase_10 AC 9 ms
4,380 KB
testcase_11 AC 1,100 ms
62,032 KB
testcase_12 AC 1,088 ms
62,064 KB
testcase_13 AC 1,092 ms
62,036 KB
testcase_14 AC 1,103 ms
62,400 KB
testcase_15 AC 1,095 ms
62,288 KB
testcase_16 AC 1,096 ms
62,264 KB
testcase_17 AC 1,093 ms
61,968 KB
testcase_18 AC 1,099 ms
61,932 KB
testcase_19 AC 1,097 ms
61,960 KB
testcase_20 AC 1,104 ms
61,920 KB
testcase_21 AC 1,453 ms
77,380 KB
testcase_22 AC 926 ms
63,892 KB
testcase_23 AC 984 ms
64,048 KB
testcase_24 AC 1,916 ms
72,036 KB
testcase_25 AC 1,055 ms
64,108 KB
testcase_26 AC 2,299 ms
72,020 KB
testcase_27 AC 1,059 ms
63,916 KB
testcase_28 AC 1,063 ms
64,104 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct LCA{
    int n,m,cnt;
    vector<vector<int> > data,e;
    vector<int> depth,vis;
    LCA(int n):n(n){
        int ni = 1;
        cnt = 0;
        while(ni<n){
            ni<<=1;
            cnt++;
        }
        data = vector<vector<int> >(n,vector<int>(cnt+1,-1));
        e = vector<vector<int> >(n);
        depth = vector<int>(n,-1);
    }

    void addedge(int a,int b){
        e[a].push_back(b);
        e[b].push_back(a);
    }

    void dfs(int ni,int p,int now){
        depth[ni] = now;
        data[ni][0] = p;
        vis[ni] = 1;
        for(int to:e[ni]) if(to!=p){
            dfs(to,ni,now+1);
        }
    }

    void build(int root = 0){
        vis = vector<int> (n,0);
        dfs(root,-1,0);
        for(int i = 0;i<n;i++) if(vis[i]==0) dfs(i,-1,0);
        for(int i = 1;i<=cnt;i++){
            for(int j = 0;j<n;j++){
                data[j][i] = data[j][i-1];
                if(data[j][i]==-1) continue;
                data[j][i] = data[data[j][i]][i-1];
            }
        }
    }

    int query(int a,int b){
        if(depth[a] > depth[b]) swap(a,b);
        int need = depth[b] - depth[a];
        int nj = 0;
        while (need!=0){
            if(need&1) b = data[b][nj];
            nj++;
            need >>= 1;
        }
        if(a==b) return a;
        int now = cnt;
        while(now>=0){
            if(data[a][now]!=data[b][now]){
                a = data[a][now];
                b = data[b][now];
            }
            now--;
        }
        return data[a][0];
    }

    int dist(int a,int b){
        int c = query(a,b);
        return depth[a] + depth[b] - 2*depth[c];
    }

    int get(int i,int k){
        int j = i;
        int now = 0;
        while(k){
            if(k&1) j = data[j][now];
            if(j==-1) return j;
            k>>=1;
            now++;
        }
        return j;
    }

};

int n,q;
vector<int> g[2<<17];
vector<int> sz[2<<17];
int nn[2<<17];

int d1(int ni,int p){
    sort(g[ni].begin(),g[ni].end());
    nn[ni]++;
    sz[ni] = vector<int>(g[ni].size(),0);
    for(int i = 0;i<g[ni].size();i++){
        if(g[ni][i]==p) continue;
        sz[ni][i] = d1(g[ni][i],ni);
        nn[ni] += sz[ni][i];
    }
    return nn[ni];
}

int d2(int ni,int p,int now){
    if(p!=-1) nn[ni] += now;
    for(int i = 0;i<g[ni].size();i++){
        if(g[ni][i]==p){
            sz[ni][i] = now;
            continue;
        }
        d2(g[ni][i],ni,nn[ni]-sz[ni][i]);
    }
    return 0;
}

int main(){
    cin>>n>>q;
    LCA lca(n);
    for(int i = 0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        u--;v--;
        g[u].push_back(v);
        g[v].push_back(u);
        lca.addedge(u,v);
    }
    d1(0,-1);
    d2(0,-1,0);
    lca.build();
    while(q--){
        int x,y;
        cin>>x>>y;
        x--;y--;
        int t = lca.query(x,y);
        int dd = lca.dist(x,y);
        if(dd%2==1){
            cout<<0<<endl;
            continue;
        }
        int nx = lca.get(x,dd/2);
        int ny = lca.get(y,dd/2);
        if(ny!=-1&&lca.dist(t,ny)+lca.dist(ny,y)==lca.dist(t,y)){
            swap(nx,ny);
            swap(x,y);
        }
        int ans = n;
        int i = lca.get(x,dd/2-1);
        int j = 0;
        if(nx==t){
            j = lca.get(y,dd/2-1);
        }else{
            j = lca.get(nx,1);
        }
        int ni = lower_bound(g[nx].begin(),g[nx].end(),i) - g[nx].begin();
        int nj = lower_bound(g[nx].begin(),g[nx].end(),j) - g[nx].begin();
        ans -= sz[nx][ni] + sz[nx][nj];
        cout<<ans<<endl;
    }
}
0