#877734 (C++17) No.2337 Equidistant

• 問題: No.2337 Equidistant
• ユーザー: asaringo
• 提出日時: 2023-06-03 01:22:18
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,342 ms / 4,000 ms
• コード長: 8,492 bytes
• コンパイル時間: 2,613 ms
• コンパイル使用メモリ: 217,196 KB
• 最終ジャッジ日時: 2025-02-13 21:57:39
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
sample	AC * 1
other	AC * 28

ソースコード

#include <bits/stdc++.h>
using namespace std ;
#define fast_input_output ios::sync_with_stdio(false); cin.tie(nullptr);
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll ;
typedef long double ld ;
typedef pair<ll,ll> P ;
typedef tuple<ll,ll,ll> TP ;
#define chmin(a,b) a = min(a,b)
#define chmax(a,b) a = max(a,b)
#define bit_count(x) __builtin_popcountll(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl
#define DEBUG(...) ; cout << #__VA_ARGS__ << endl ; for(auto x : {__VA_ARGS__}) cout << x << "  " ; cout << endl ;
#define DEBUG_LIST(...) cout << #__VA_ARGS__ << endl ; DEBUG_REP(__VA_ARGS__) ;
#define DEBUG_REP(V) cout << "{ " ; repi(itr,V) cout << *itr << ", " ; cout << "}" << endl ;
#define debug(a) cout << #a << " " << a << endl
#define all(a) a.begin(), a.end()
#define endl "\n"

struct TreeDiameter{
    private :
        vector<vector<int>> G ;
        int n , diameter ;
        // start_node: 直径の端点1, end_node: 直径の端点2, lca: 直径の端点1,2の共通祖先(木の直径の中心)
        int start_node , end_node , lca , lcb;
        vector<int> dist , parent ;

        void init_() {
            dist.resize(n) ;
            parent.resize(n) ;
            G.resize(n) ;
        }

        void init_(int n_) {
            n = n_ ;
            dist.resize(n) ;
            parent.resize(n) ;
            G.resize(n) ;
        }

        void add_edge_(int v , int u){
            G[u].push_back(v) ;
            G[v].push_back(u) ;
        }

        void build_() {
            dfs(0,-1,0) ;
            int maxval = -1 ;
            start_node = -1 ;
            for(int i = 0 ; i < n ; i++) {
                if(maxval < dist[i]){
                    maxval = dist[i] ;
                    start_node = i ;
                }
                dist[i] = 0 ;
            }
            dfs(start_node,-1,0) ;
            diameter = -1 ;
            end_node = -1 ;
            for(int i = 0 ; i < n ; i++) {
                if(diameter < dist[i]){
                    diameter = dist[i] ;
                    end_node = i ;
                }
            }
            get_lca_() ;
        }

        void dfs(int v , int prev , int dep){
            dist[v] = dep ;
            parent[v] = prev ;
            for(int i = 0 ; i < G[v].size() ; i++){
                int u = G[v][i] ;
                if(u == prev) continue ;
                dfs(u,v,dep+1) ;
            }
        }

        void get_lca_(){
            int v = end_node;
            int count = 0 ;
            while(v != -1){
                if(count == diameter / 2) lca = v ;
                if(count == (diameter + 1) / 2) lcb = v ;
                v = parent[v] ;
                count++ ;
            }
        }
    
    public :
        // コンストラクタ
        TreeDiameter(int n_): n(n_) { init_() ; }
        // コンストラクタ
        TreeDiameter() {}
        // 初期化
        void init(int n_) { init_(n_) ; }
        // 辺を張る
        void add_edge(int v , int u) { add_edge_(v,u) ; }
        // ビルドする
        void build() { build_() ; }
        // グラフを得る
        vector<vector<int>> get_graph() { return G ; }
        // 木の直径を取得
        int get_diameter() {return diameter ; }
        // 木の直径を生成する共通祖先のノードを取得(木の中心を取得)
        int get_lca(){ return lca ; }
        int get_lcb(){ return lcb ; }
        // 木の直径を生成する2つのノード
        P get_end_node() { return P(start_node,end_node) ; }
};

struct LCA{
    private :
        int n ;
        vector<int> dist ;
        vector<vector<int>> parent ;
        vector<vector<int>> G ;

        void build_() {
            dfs(0,-1,0) ;
            for(int i = 0 ; i < 19 ; i++){
                for(int node = 0 ; node < n ; node++){
                    if(parent[node][i] >= 0) parent[node][i+1] = parent[parent[node][i]][i] ;
                }
            }
        }

        void add_edge_(int u , int v){
            G[v].push_back(u) ;
            G[u].push_back(v) ;
        }

        //深さ優先探索
        void dfs(int v , int prev , int d){
            dist[v] = d ;
            parent[v][0] = prev ;
            for(int i = 0 ; i < G[v].size() ; i++){
                int u = G[v][i] ;
                if(dist[u] == -1){
                    dfs(u,v,d+1) ;
                }
            }
        }

        //k個前のノードを求める
        int prev_k_(int v, int k){
            for(int i = 0; i < 19; i++) if(k >> i & 1) {
                v = parent[v][i];
                if(v == -1) return v;
            }
            return v;
        }

        //LCAを求める
        int get_lca_(int u , int v){
            if(dist[u] < dist[v]) swap(u,v) ;
            for(int i = 0 ; i < 20 ; i++){
                if((dist[v] - dist[u]) >> i & 1) u = parent[u][i] ;
            }
            if(u == v) return u ;
            for(int i = 19 ; i >= 0 ; i--){
                if(parent[u][i] != parent[v][i]){
                    u = parent[u][i] ;
                    v = parent[v][i] ;
                }
            }
            return parent[u][0] ;
        }

        //距離を求める
        int dist_u_to_v_(int u , int v){
            int node = get_lca(u,v) ;
            return dist[u] + dist[v] - 2*dist[node] ;
        }

        //u-vパス上に頂点nodeが存在するか
        bool node_is_on_path_(int u , int v , int node){
            return dist_u_to_v(u,v) == dist_u_to_v(u,node) + dist_u_to_v(node,v) ;
        }

    public :
        LCA(int n_){
            n = n_ ;
            dist.resize(n,-1) ;
            parent.resize(n,vector<int>(30,-1)) ;
            G.resize(n) ;
        }
        void build() { build_() ; }
        void add_edge(int u , int v) { add_edge_(u,v) ; }
        int prev_k(int v, int k) { return prev_k_(v,k); }
        int get_lca(int u , int v) { return get_lca_(u,v) ; }
        int dist_u_to_v(int u , int v) { return dist_u_to_v_(u,v) ; }
        bool node_is_on_path(int u , int v , int node){ return node_is_on_path_(u,v,node) ; }
        vector<vector<int>> get_gragh() { return G ; }
};

// function                  : return              : description
// -----------------------------------------------------
// build()                   : void                : ビルドする (辺を張った後にビルドすることに注意)
// add_edge(u,v)             : void                : u -> v, v -> u に辺を張る
// get_lca(u,v)              : int                 : u と v の LCA を求める
// dist_u_to_v(u,v)          : int                 : u と v の距離を求める
// node_is_on_path(u,v,node) : bool                : u と v のパス上に node があるか
// get_gragh                 : vector<vector<int>> : グラフ G を返す
// *注意* 取り敢えず全てをコピペすることを奨励

// ------------------------- //
// 不安であれば ABC014D で確認  //
// ------------------------- //

int depth[202020];
int D[202020];

int n, q;
vector<vector<int>> G;

void dfs(int v, int prev, int dep){
    int res = 0;
    depth[v] = dep;
    for(int u : G[v]){
        if(u == prev) continue;
        dfs(u,v,dep+1);
        res += D[u];
    }
    D[v] = res + 1;
}

int main(){
    cin >> n >> q;
    LCA lca(n) ;
    rep(i,n-1){
        int u , v ;
        cin >> u >> v ;
        u-- ; v-- ;
        lca.add_edge(u,v) ;
    }
    // グラフを取得
    G = lca.get_gragh() ;
    // ビルドをする
    lca.build();
    dfs(0,-1,0);
    rep(i,q){
        int a, b;
        cin >> a >> b;
        a--; b--;
        int dist = lca.dist_u_to_v(a,b);
        if(dist % 2 == 1){
            cout << 0 << endl;
            continue;
        }
        dist /= 2;
        if(depth[a] < depth[b]) swap(a,b);
        int node = lca.prev_k(a,dist);
        if(depth[a] == depth[b]){
            int v = lca.prev_k(a,dist-1);
            int u = lca.prev_k(b,dist-1);
            cout << n - D[u] - D[v] << endl;
        }
        else{
            int v = lca.prev_k(a,dist-1);
            cout << D[node] - D[v] << endl;
        }
    }
}