結果
| 問題 |
No.1212 Second Path
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:04:28 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,493 bytes |
| コンパイル時間 | 2,394 ms |
| コンパイル使用メモリ | 110,664 KB |
| 実行使用メモリ | 38,104 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:21 |
| 合計ジャッジ時間 | 11,790 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | TLE * 1 -- * 44 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map> // Using map to store edges on the path for quick lookup
#include <vector> // Standard vectors usage
using namespace std;
// Define long long for large edge weights and path lengths
typedef long long ll;
// Define a large value for infinity, suitable for sums of edge weights up to 10^9
// N <= 10^5, max path length could be N-1. Path length * 2 could exceed 32-bit int.
// A path could have length up to (N-1)*10^9. Plus detour 2*10^9. Still fits in 64-bit ll.
// Use a value larger than any possible path length. Max path length roughly 10^5 * 10^9 = 10^14.
// Add detour max 2*10^9. So result fits in ll. INF needs to be larger. 4e18 is safe.
const ll INF = 4e18;
// Structure to represent an edge in the adjacency list
struct Edge {
int to; // Neighbor vertex
ll weight; // Edge weight
};
vector<vector<Edge>> adj; // Adjacency list representation of the tree
// Variables needed for LCA (Lowest Common Ancestor) calculation using binary lifting
vector<int> parent; // parent[u] stores the parent of node u in the BFS tree from root
vector<ll> dist_from_root; // dist_from_root[u] stores the distance from root (node 1) to node u
vector<int> depth; // depth[u] stores the depth of node u (distance in edges from root)
vector<vector<int>> ancestor; // ancestor[k][u] stores the 2^k-th ancestor of node u
int MAX_LOG_N; // Maximum power of 2 needed for binary lifting, depends on N
// Performs BFS starting from a given root to compute depths, parents, and distances
// Also preprocesses the first level parents for binary lifting LCA
void bfs_lca(int root, int N) {
// Initialize vectors
depth.assign(N + 1, -1); // -1 indicates unvisited
parent.assign(N + 1, 0); // Parent of root is 0 (pseudo node)
dist_from_root.assign(N + 1, 0); // Distance from root to itself is 0
depth[root] = 0; // Root is at depth 0
queue<int> q;
q.push(root);
depth[0] = -1; // Set depth of pseudo parent node 0 to -1
// Standard BFS traversal
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& edge : adj[u]) {
int v = edge.to;
if (depth[v] == -1) { // If neighbor v is not visited
depth[v] = depth[u] + 1; // Set depth
parent[v] = u; // Set parent
dist_from_root[v] = dist_from_root[u] + edge.weight; // Update distance from root
q.push(v); // Add neighbor to queue
}
}
}
// Precompute ancestors for binary lifting LCA
MAX_LOG_N = 0;
while ((1 << MAX_LOG_N) <= N) {
MAX_LOG_N++;
}
// Resize ancestor table: MAX_LOG_N levels, N+1 nodes
ancestor.assign(MAX_LOG_N, vector<int>(N + 1, 0));
// Base case: 2^0 = 1st ancestor is the direct parent
for (int i = 1; i <= N; ++i) {
ancestor[0][i] = parent[i];
}
// Dynamically compute 2^k-th ancestors using 2^(k-1)-th ancestors
for (int k = 1; k < MAX_LOG_N; ++k) {
for (int i = 1; i <= N; ++i) {
// Check if the 2^(k-1)-th ancestor exists
if (ancestor[k - 1][i] != 0) {
// The 2^k-th ancestor is the 2^(k-1)-th ancestor of the 2^(k-1)-th ancestor
ancestor[k][i] = ancestor[k - 1][ancestor[k - 1][i]];
}
}
}
}
// Computes the Lowest Common Ancestor (LCA) of two nodes u and v using binary lifting
int lca(int u, int v) {
// Ensure u is the deeper node, swap if needed
if (depth[u] < depth[v]) {
swap(u, v);
}
// Lift node u up until it's at the same depth as node v
for (int k = MAX_LOG_N - 1; k >= 0; --k) {
// Check if 2^k-th ancestor exists and lifting doesn't overshoot v's depth
if (ancestor[k][u] != 0 && depth[u] - (1 << k) >= depth[v]) {
u = ancestor[k][u]; // Lift u
}
}
// If u and v are now the same node, it's the LCA
if (u == v) {
return u;
}
// Lift u and v simultaneously maintaining the property that their parents might be LCA
for (int k = MAX_LOG_N - 1; k >= 0; --k) {
// If their 2^k-th ancestors are different, lift both
if (ancestor[k][u] != ancestor[k][v]) {
u = ancestor[k][u];
v = ancestor[k][v];
}
}
// After the loop, u and v are children of the LCA. Return parent of u (or v).
return parent[u];
}
// Computes the distance between nodes u and v using their distances from root and LCA
ll get_dist(int u, int v) {
int l = lca(u, v); // Find LCA
// Distance formula: dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, lca(u, v))
return dist_from_root[u] + dist_from_root[v] - 2 * dist_from_root[l];
}
// Global list to store nodes on the current query path
vector<int> path_nodes_list;
// Map to store edges on the current query path for O(log N) or O(1) avg lookup
// Key is pair {min(u,v), max(u,v)} representing an undirected edge
map<pair<int, int>, bool> on_path_edge_map;
// Helper function to reconstruct path segment from node u up to target_ancestor (exclusive)
// Adds nodes to path_nodes_list and edges to on_path_edge_map
void find_path_info(int u, int target_ancestor) {
int curr = u;
while (curr != target_ancestor) { // Keep climbing until target ancestor is reached
path_nodes_list.push_back(curr); // Add current node to path list
int p = parent[curr]; // Get parent
if (p != 0) { // Check if parent is valid (not pseudo node 0)
// Store edge {curr, p} in map using canonical representation {min, max}
int u1 = min(curr, p), v1 = max(curr, p);
on_path_edge_map[{u1, v1}] = true;
}
curr = p; // Move up to parent
if(curr == 0) break; // Safety break: should not happen in a connected tree with nodes 1..N
}
}
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of vertices
cin >> N;
adj.resize(N + 1); // Resize adjacency list
// Read N-1 edges
for (int i = 0; i < N - 1; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
// Add edge to adjacency list for both directions (undirected graph)
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
// Precompute LCA related structures (depth, parent, distance, ancestor table)
bfs_lca(1, N); // Root the tree arbitrarily at node 1
int Q; // Number of queries
cin >> Q;
// Pre-allocate space for path nodes list for potential efficiency gain
path_nodes_list.reserve(N);
// Process each query
while (Q--) {
int x, y; // Start and end vertices for the query
cin >> x >> y;
// Calculate the shortest path distance between x and y
ll shortest_dist = get_dist(x, y);
// Clear data structures from previous query
path_nodes_list.clear();
on_path_edge_map.clear();
// Find the LCA of x and y
int l = lca(x, y);
// Reconstruct the simple path from x to LCA and mark nodes/edges
find_path_info(x, l);
// Reconstruct the simple path from y to LCA and mark nodes/edges
find_path_info(y, l);
// Add the LCA node itself to the list of path nodes
path_nodes_list.push_back(l);
// Variable to store the minimum added length for the second shortest path
ll min_added_len = INF;
// Map to keep track of nodes already processed to avoid redundant checks
map<int, bool> processed_nodes;
// Iterate through each unique node u on the simple path P_xy
for (int u : path_nodes_list) {
// Skip node 0 (if ever appears) or nodes already processed
if (u == 0 || processed_nodes[u]) continue;
processed_nodes[u] = true; // Mark node u as processed
// Iterate through all edges incident to node u
for (const auto& edge : adj[u]) {
int v = edge.to; // Neighbor vertex
ll w = edge.weight; // Edge weight
// Canonical representation of the edge {u, v}
int u1 = min(u, v), v1 = max(u, v);
// Check if this edge {u, v} is part of the simple path P_xy
if (on_path_edge_map.find({u1, v1}) == on_path_edge_map.end()) {
// If the edge is NOT on the simple path P_xy:
// It can be used for a detour u -> v -> u.
// This adds 2 * w to the total path length.
// Update the minimum added length found so far.
min_added_len = min(min_added_len, 2 * w);
}
}
}
// Output the result for the query
if (min_added_len == INF) {
// If min_added_len is still INF, it means no valid detour edge was found.
// This typically happens if the simple path P_xy uses all edges connected to its nodes.
// E.g., the tree is just a path graph and x, y are its endpoints.
cout << -1 << "\n";
} else {
// The second shortest path length is the shortest path length plus the minimum detour cost.
cout << shortest_dist + min_added_len << "\n";
}
}
return 0;
}