#1083887 (C++17) No.1787 Do Use Dynamic Tree

• 問題: 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
}