結果
| 問題 |
No.1787 Do Use Dynamic Tree
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:07:14 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,812 bytes |
| コンパイル時間 | 1,206 ms |
| コンパイル使用メモリ | 78,728 KB |
| 実行使用メモリ | 23,532 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:01 |
| 合計ジャッジ時間 | 15,883 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 26 TLE * 1 -- * 11 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <vector>
// Define the maximum number of vertices based on problem constraints
const int MAXN = 200005;
// Adjacency list to represent the tree structure. adj[i] stores neighbors of vertex i.
std::vector<int> adj[MAXN];
// Array to store the values written on vertices. Use long long for safety, although N <= 2e5 fits in int.
long long values[MAXN];
int N; // Number of vertices in the tree
/**
* @brief Finds the best neighbor to move to from vertex u, avoiding vertex p.
*
* The "best" neighbor is defined by the following rules:
* 1. It must have the maximum possible value among all neighbors of u (excluding p).
* 2. If there is a tie (multiple neighbors have the same maximum value), the one with the largest vertex ID is chosen.
*
* @param u The current vertex.
* @param p The previous vertex in the path traversal (to avoid going back). Use 0 if u is the starting vertex.
* @return The vertex ID of the best neighbor. Returns -1 if no valid neighbor exists (e.g., u is a leaf in the traversal direction).
*/
inline int find_best_neighbor_simple(int u, int p) {
long long max_val = -1; // Initialize max value found so far to -1 (since vertex values are positive integers).
int best_neighbor_id = -1; // Initialize best neighbor ID found so far to -1.
// Iterate through all neighbors of vertex u
for (int v : adj[u]) {
// Skip the neighbor if it's the vertex p we just came from
if (v == p) continue;
long long current_val = values[v]; // Get the value of the neighbor vertex v
// Check if the current neighbor's value is greater than the maximum value found so far
if (current_val > max_val) {
max_val = current_val; // Update the maximum value
best_neighbor_id = v; // Update the best neighbor ID
}
// Check if the current neighbor's value is equal to the maximum value (a tie)
else if (current_val == max_val) {
// Apply the tie-breaking rule: choose the neighbor with the larger vertex ID.
// This comparison `v > best_neighbor_id` correctly handles the initial state where best_neighbor_id is -1,
// because any valid vertex ID v (>= 1) will be greater than -1.
if (v > best_neighbor_id) {
best_neighbor_id = v; // Update best_neighbor_id if v has a larger ID
}
}
}
// Return the ID of the best neighbor found according to the rules.
// If no valid neighbor was found (e.g., u is a leaf node when viewed from p), returns -1.
return best_neighbor_id;
}
/**
* @brief Solves a single query to find the vertex w that maximizes the sequence f(u, w) lexicographically.
*
* This function implements a greedy strategy: Starting from vertex u, it repeatedly moves to the "best" neighbor
* (determined by find_best_neighbor_simple) until it cannot move further. The vertex where this path ends is returned as the answer.
* The rationale is that maximizing the sequence lexicographically heavily prioritizes earlier elements, which aligns with
* greedily choosing the neighbor with the highest value at each step. The vertex ID tie-breaking ensures a unique path is chosen.
* The final node of this path is taken as the argmax_w f(u, w).
*
* @param u The starting vertex for the paths f(u, w).
* @return The vertex ID w that maximizes f(u, w) lexicographically based on the greedy strategy.
*/
inline int solve_query(int u) {
int current_node = u; // Start the path traversal from vertex u.
int prev_node = 0; // Use 0 as a placeholder for the parent of the starting node (no parent initially).
while (true) {
// Find the best neighbor to move to from the current node, ensuring we don't move back to the previous node.
int next_node = find_best_neighbor_simple(current_node, prev_node);
// If find_best_neighbor_simple returns -1, it signifies that there are no valid neighbors to continue the path.
// This occurs if current_node is a leaf in the direction away from prev_node.
if (next_node == -1) {
break; // Terminate the path construction process.
}
// Move to the determined best neighbor.
prev_node = current_node; // Update the previous node to the current node.
current_node = next_node; // Update the current node to the chosen next node.
}
// The loop terminates when the path cannot be extended further following the greedy rule.
// The 'current_node' at this point is the endpoint 'w' of the constructed path.
return current_node;
}
int main() {
// Set up fast input/output
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read the number of vertices N
std::cin >> N;
// Read N-1 edges to build the tree structure using an adjacency list
for (int i = 0; i < N - 1; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v); // Add edge between u and v
adj[v].push_back(u); // Add edge between v and u (undirected graph)
}
// Initialize the values array: vertex i initially holds the value i
for (int i = 1; i <= N; ++i) {
values[i] = i;
}
// Read the number of queries Q
int Q;
std::cin >> Q;
// Variable to store the answer of the previous query, needed for query decryption
long long last_ans = 0;
// Process each of the Q queries
for (int i = 0; i < Q; ++i) {
long long u_raw, v_raw; // Read the raw (encrypted) query vertices
std::cin >> u_raw >> v_raw;
// Decrypt the query vertices using the provided formula and the answer from the previous query
// The formula is: result = (((raw_input + N - 1 + last_ans) % N) + 1)
long long u_true = ((u_raw + N - 1 + last_ans) % N) + 1;
long long v_true = ((v_raw + N - 1 + last_ans) % N) + 1;
// Perform the swap operation on the values at the decrypted vertices u_true and v_true.
// Check if u_true and v_true are different before swapping, as swapping a value with itself is pointless
// and std::swap typically requires distinct memory locations (though it might work correctly anyway).
if (u_true != v_true) {
std::swap(values[u_true], values[v_true]);
}
// Call the solve_query function with the decrypted starting vertex u_true
// to find the vertex w that maximizes f(u_true, w).
last_ans = solve_query(u_true);
// Output the result (the vertex ID w) for the current query, followed by a newline.
std::cout << last_ans << "\n";
}
return 0; // Indicate successful execution
}