結果

問題 No.2337 Equidistant
ユーザー momoyuumomoyuu
提出日時 2023-06-02 22:57:16
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,581 bytes
コンパイル時間 3,806 ms
コンパイル使用メモリ 261,412 KB
実行使用メモリ 80,768 KB
最終ジャッジ日時 2024-06-09 00:50:00
合計ジャッジ時間 26,403 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 5 ms
5,376 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 AC 910 ms
64,156 KB
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
権限があれば一括ダウンロードができます

ソースコード

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];
            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(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