結果

問題 No.2337 Equidistant
ユーザー hiro71687khiro71687k
提出日時 2023-06-02 22:30:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,729 ms / 4,000 ms
コード長 5,103 bytes
コンパイル時間 2,429 ms
コンパイル使用メモリ 214,400 KB
実行使用メモリ 120,764 KB
最終ジャッジ日時 2023-08-28 04:29:28
合計ジャッジ時間 24,722 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 7 ms
4,380 KB
testcase_07 AC 7 ms
4,380 KB
testcase_08 AC 8 ms
4,540 KB
testcase_09 AC 8 ms
4,376 KB
testcase_10 AC 8 ms
4,376 KB
testcase_11 AC 1,028 ms
106,524 KB
testcase_12 AC 1,010 ms
106,320 KB
testcase_13 AC 1,030 ms
106,420 KB
testcase_14 AC 1,032 ms
106,532 KB
testcase_15 AC 1,023 ms
106,656 KB
testcase_16 AC 1,010 ms
106,332 KB
testcase_17 AC 1,004 ms
106,264 KB
testcase_18 AC 1,023 ms
106,276 KB
testcase_19 AC 1,021 ms
106,292 KB
testcase_20 AC 1,011 ms
106,392 KB
testcase_21 AC 1,264 ms
120,764 KB
testcase_22 AC 812 ms
106,892 KB
testcase_23 AC 912 ms
107,164 KB
testcase_24 AC 1,529 ms
115,896 KB
testcase_25 AC 950 ms
107,352 KB
testcase_26 AC 1,729 ms
115,560 KB
testcase_27 AC 988 ms
107,212 KB
testcase_28 AC 981 ms
107,116 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
ld pie=3.141592653589793;
ll inf=2000000000000000000;
ll mod=998244353;
/* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor を求める構造体
    query(u,v): u と v の LCA を求める。計算量 O(logn)
    前処理: O(nlogn)時間, O(nlogn)空間
*/
struct LCA {
    vector<vector<long long>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<ll> dist;            // root からの距離
    LCA(vector<vector<ll>> &G, ll root = 0) { init(G, root); }

    // 初期化
    void init(vector<vector<ll>> &G, int root = 0) {
        ll V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, vector<ll>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(vector<vector<ll>> &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e != p) dfs(G, e, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};
ll dfs(ll now,vector<ll>&m,vector<vector<ll>>&g){
    m[now]=-1;
    ll x=1;
    for (ll i = 0; i < g[now].size(); i++)
    {
        if (m[g[now][i]]==-1)
        {
            continue;
        }
        x+=dfs(g[now][i],m,g);
    }
    m[now]=x;
    return x;
}
int main(){
    ll n,q;
    cin >> n >> q;
    vector<vector<ll>>g(n);
    for (ll i = 0; i < n-1; i++)
    {
        ll a,b;
        cin >> a >> b;
        a--,b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<ll>m(n,0);
    dfs(0,m,g);
    queue<ll>que;
    vector<ll>memo(n,inf);
    memo[0]=0;
    que.push(0);
    while (!que.empty())
    {
        ll v=que.front();
        que.pop();
        for (ll i = 0; i < g[v].size(); i++)
        {
            if (memo[g[v][i]]>memo[v]+1)
            {
                memo[g[v][i]]=memo[v]+1;
                que.push(g[v][i]);
            }
        }
    }
    LCA lca(g,0);
    vector<ll>ans;
    vector<vector<ll>>db(n,vector<ll>(30,-1));
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < g[i].size(); j++)
        {
            if (memo[g[i][j]]==memo[i]-1)
            {
                db[i][0]=g[i][j];
                break;
            }
        }
    }
    for (ll j = 1; j < 30; j++)
    {
        for (ll i = 0; i < n; i++)
        {
            if (db[i][j-1]==-1)
            {
                continue;
            }
            db[i][j]=db[db[i][j-1]][j-1];
        }
    }
    vector<ll>two(40,1);
    for (ll i = 1; i < 40; i++)
    {
        two[i]=two[i-1]*2;
    }
    for (ll i = 0; i < q; i++)
    {
        ll s,t;
        cin >> s >> t;
        s--,t--;
        ll x=lca.query(s,t);
        ll a=memo[s]-memo[x];
        ll b=memo[t]-memo[x];
        if (a%2!=b%2)
        {
            ans.push_back(0);
        }else if (a==b)
        {
            if (a==1)
            {
                ans.push_back(n-m[s]-m[t]);
                continue;
            }
            a--;
            b--;
            ll xx=s;
            for (ll j = 0; j < 30; j++)
            {
                if (a&two[j])
                {
                    xx=db[xx][j];
                }
            }
            ll yy=t;
            for (ll j = 0; j < 30; j++)
            {
                if (b&two[j])
                {
                    yy=db[yy][j];
                }
            }
            ans.push_back(n-m[xx]-m[yy]);
        }else{
            ll now,y;
            if (a>b)
            {
                now=s,y=(a+b)/2;
            }else{
                now=t,y=(b+a)/2;
            }
            ll nn=now;
            for (ll j = 0; j < 30; j++)
            {
                if (y&two[j])
                {
                    now=db[now][j];
                }
            }
            y--;
            for (ll j = 0; j < 30; j++)
            {
                if (y&two[j])
                {
                    nn=db[nn][j];
                }
            }
            ans.push_back(m[now]-m[nn]);
        }
    }
    for (ll i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << endl;
    }

}
0