結果
| 問題 |
No.2337 Equidistant
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:55:52 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 440 ms / 4,000 ms |
| コード長 | 10,142 bytes |
| コンパイル時間 | 670 ms |
| コンパイル使用メモリ | 95,548 KB |
| 実行使用メモリ | 46,592 KB |
| 最終ジャッジ日時 | 2025-05-14 12:57:28 |
| 合計ジャッジ時間 | 7,363 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <vector>
// Use MAXN slightly larger than 200,000 for safety, e.g., 200005
const int MAXN = 200005;
// log2(200000) is approx 17.6, so 18 levels are needed for binary lifting.
const int LOGN = 18;
std::vector<int> adj[MAXN]; // Adjacency list for the tree
int parent[MAXN]; // Stores the direct parent of each node in DFS traversal rooted at 1
int depth[MAXN]; // Stores the depth of each node (distance from root 1)
int subtree_size[MAXN]; // Stores the size of the subtree rooted at each node in the DFS tree
int up[MAXN][LOGN]; // Binary lifting table: up[u][i] is the 2^i-th ancestor of u
/**
* @brief Performs Depth First Search starting from node u to compute properties needed for LCA and subtree calculations.
*
* @param u Current node being visited.
* @param p Parent of the current node in DFS traversal.
* @param d Depth of the current node.
*/
void dfs(int u, int p, int d) {
parent[u] = p; // Set parent
depth[u] = d; // Set depth
subtree_size[u] = 1; // Initialize subtree size with the node itself
up[u][0] = p; // Base case for binary lifting: 2^0 = 1st ancestor is the parent
// Precompute higher ancestors using binary lifting dynamic programming
for (int i = 1; i < LOGN; ++i) {
// The 2^i-th ancestor is the 2^(i-1)-th ancestor of the 2^(i-1)-th ancestor
// Check if the (i-1)-th ancestor exists (is not 0, our dummy node above root)
if (up[u][i-1] != 0) {
up[u][i] = up[up[u][i-1]][i-1];
} else {
// If ancestor at level 2^(i-1) doesn't exist, then ancestor at level 2^i also doesn't exist
up[u][i] = 0;
}
}
// Recurse for children
for (int v : adj[u]) {
if (v != p) { // Avoid going back up to the parent
dfs(v, u, d + 1);
subtree_size[u] += subtree_size[v]; // Update subtree size by adding sizes of children's subtrees
}
}
}
/**
* @brief Finds the k-th ancestor of node u using binary lifting.
*
* @param u The node whose ancestor is to be found.
* @param k The level of ancestor required (k=1 means parent, k=2 means grandparent etc.).
* @return The k-th ancestor node ID, or 0 if the k-th ancestor is above the root.
*/
int get_ancestor(int u, int k) {
// Check for invalid k or if u is already 0 (a possible state if previous jump went above root)
if (k < 0 || u == 0) return 0;
if (k == 0) return u; // 0-th ancestor is the node itself
// Use binary lifting to jump up k levels efficiently
for (int i = LOGN - 1; i >= 0; --i) {
// If 2^i is less than or equal to the remaining distance k
// This checks if the i-th bit of k is set
if ((k >> i) & 1) {
u = up[u][i]; // Jump up by 2^i levels
// If we jumped above the root (reached node 0), stop
if (u == 0) break;
}
}
return u; // Return the k-th ancestor found
}
/**
* @brief Finds the Lowest Common Ancestor (LCA) of nodes u and v.
*
* @param u First node.
* @param v Second node.
* @return The LCA node ID.
*/
int lca(int u, int v) {
// Ensure u is the deeper node by swapping if necessary
if (depth[u] < depth[v]) {
std::swap(u, v);
}
// Bring u up to the same depth as v using get_ancestor
u = get_ancestor(u, depth[u] - depth[v]);
// If u and v are the same node now, they are the LCA
if (u == v) {
return u;
}
// Jump u and v up simultaneously using binary lifting
// Find the highest ancestors of u and v that are different
for (int i = LOGN - 1; i >= 0; --i) {
if (up[u][i] != up[v][i]) { // If 2^i-th ancestors are different
u = up[u][i]; // Jump u up
v = up[v][i]; // Jump v up
}
}
// After the loop, u and v are direct children of the LCA
// The LCA is the parent of u (or v)
return up[u][0];
}
/**
* @brief Calculates the distance (number of edges) between nodes u and v in the tree.
*
* @param u First node.
* @param v Second node.
* @return The distance between u and v.
*/
int dist(int u, int v) {
int common_ancestor = lca(u, v);
// Standard tree distance formula: dist(u,v) = depth(u) + depth(v) - 2*depth(lca(u,v))
return depth[u] + depth[v] - 2 * depth[common_ancestor];
}
int main() {
// Use fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of vertices
int Q; // Number of queries
std::cin >> N >> Q;
// Read edges and build adjacency list representation of the tree
for (int i = 0; i < N - 1; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Precomputation step: Perform DFS starting from root 1
// This computes depths, parents, subtree sizes, and initializes binary lifting table
dfs(1, 0, 0); // Assuming root is 1, its parent is 0 (dummy node), depth is 0
// Process each query
for (int i = 0; i < Q; ++i) {
int S, T; // Query vertices
std::cin >> S >> T;
// Calculate distance between S and T
int d_ST = dist(S, T);
// If distance is odd, no vertex can be equidistant. The answer is 0.
if (d_ST % 2 != 0) {
std::cout << 0 << "\n";
} else {
// If distance is even, there is a unique midpoint vertex M on the path S-T.
int k = d_ST / 2; // Half the distance
int common_ancestor = lca(S, T); // Find LCA of S and T
int d_S_L = depth[S] - depth[common_ancestor]; // Distance from S to LCA
int M; // The midpoint vertex M
// Determine the midpoint vertex M based on its position relative to S, T, and LCA
if (d_S_L == k) { // Case 1: M is the LCA itself. This happens when S and T are equidistant from LCA.
M = common_ancestor;
} else if (d_S_L > k) { // Case 2: M is on the path from S to LCA (M is a proper ancestor of S). S is further than k from LCA.
M = get_ancestor(S, k); // M is the k-th ancestor of S
} else { // Case 3: M is on the path from LCA to T (M is a proper ancestor of T). S is closer than k to LCA.
// Since d(S,M)=k and path is S->LCA->M, d(S,LCA)+d(LCA,M)=k.
// Also d(T,M)=k. M is k-th ancestor of T.
M = get_ancestor(T, k); // M is the k-th ancestor of T
}
// Find neighbors P_S and P_T of M on the unique path between S and T.
// P_S is the neighbor towards S, P_T is the neighbor towards T.
int P_S, P_T;
// Determine P_S and P_T based on which case M falls into.
if (M == common_ancestor) { // Case 1: M = LCA
// Path: S... -> P_S -> M -> P_T -> ...T
// P_S is the child of M towards S. P_T is the child of M towards T.
// Since d(S, M)=k, P_S is (k-1)th ancestor of S. (k>=1 because S!=T)
P_S = get_ancestor(S, k - 1);
// Since d(T, M)=k, P_T is (k-1)th ancestor of T.
P_T = get_ancestor(T, k - 1);
} else if (lca(S, M) == M) { // Case 2: M is an ancestor of S (and M != LCA, since d_S_L > k). Path S -> M -> LCA -> T.
// Path: S... -> P_S -> M -> P_T -> ...LCA -> ...T
// P_S is child of M towards S. P_T is parent of M towards LCA.
P_S = get_ancestor(S, k - 1); // P_S is (k-1)th ancestor of S
P_T = parent[M]; // P_T is the parent of M based on DFS tree rooted at 1
} else { // Case 3: M is an ancestor of T (and M != LCA, since d_S_L < k). Path S -> LCA -> M -> T.
// Path: S... -> LCA -> ... -> P_S -> M -> P_T -> ...T
// P_S is parent of M towards LCA. P_T is child of M towards T.
P_S = parent[M]; // P_S is the parent of M
P_T = get_ancestor(T, k - 1); // P_T is (k-1)th ancestor of T
}
// Compute sizes of components/subtrees associated with P_S and P_T relative to M.
// These represent the sets of vertices closer to S and T respectively.
long long size_M_PS, size_M_PT;
// Calculate size of the component containing P_S if edge (M, P_S) is removed.
// This depends on whether M is parent of P_S or vice-versa in the DFS tree.
if (P_S == 0) { // Edge case check, should not happen if S!=T, D>=2
size_M_PS = 0;
} else if (parent[P_S] == M) { // If M is the parent of P_S in the rooted DFS tree
size_M_PS = (long long)subtree_size[P_S]; // The size is simply the precomputed subtree size of P_S
} else { // P_S must be the parent of M
// The component containing P_S consists of all nodes *except* those in the subtree rooted at M.
size_M_PS = (long long)N - subtree_size[M];
}
// Calculate size of the component containing P_T if edge (M, P_T) is removed.
if (P_T == 0) { // Edge case check
size_M_PT = 0;
} else if (parent[P_T] == M) { // If M is the parent of P_T
size_M_PT = (long long)subtree_size[P_T]; // Size is the subtree size of P_T
} else { // P_T must be the parent of M
size_M_PT = (long long)N - subtree_size[M]; // Size is N minus the subtree size of M
}
// The number of vertices X such that d(X,S)=d(X,T) is the total number of vertices N
// minus the sizes of the components "closer" to S (rooted at P_S relative to M)
// and "closer" to T (rooted at P_T relative to M).
long long total_nodes = N;
long long answer = total_nodes - size_M_PS - size_M_PT;
std::cout << answer << "\n";
}
}
return 0;
}