結果
| 問題 |
No.912 赤黒木
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:14:07 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,355 bytes |
| コンパイル時間 | 1,065 ms |
| コンパイル使用メモリ | 88,240 KB |
| 実行使用メモリ | 43,860 KB |
| 最終ジャッジ日時 | 2025-05-14 13:15:21 |
| 合計ジャッジ時間 | 7,570 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 10 WA * 20 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
// Use vectors for adjacency lists
std::vector<std::vector<int>> adj_R; // Adjacency list for the Red Tree T_R
// No need to store the adjacency list for the Black Tree T_B fully, only degrees are needed.
std::vector<std::vector<int>> adj_G_prime; // Adjacency list for the forest G' formed by the required red edges/paths
// Store degrees for vertices based on black edges
std::vector<int> degree_B;
// Flag for vertices with odd degree in the black graph (identifies the set O_B)
std::vector<bool> is_odd_B;
// Stores the count of O_B vertices in the subtree rooted at each node in T_R during DFS
std::vector<int> subtree_odd_count;
// Visited flags for the second DFS traversal on G' (the forest)
std::vector<bool> visited;
// C(O_B): The cost of the minimum weight perfect matching on the set O_B.
// This is computed as the sum of weights (which are 1 for each edge) of red edges
// that are part of the paths connecting matched pairs in O_B.
long long C_OB = 0;
// max_path_len: The maximum length among all paths in the forest G'.
// This corresponds to the maximum weight edge in the minimum weight perfect matching M on O_B.
int max_path_len = 0;
/**
* @brief First DFS on the Red Tree (T_R).
* Computes the size of O_B within each subtree.
* Calculates the total cost C(O_B) based on subtree counts.
* Builds the adjacency list for the forest G' which represents the paths of the matching.
*
* @param u Current node being visited.
* @param p Parent node in the DFS traversal (to avoid going back up).
*/
void dfs1(int u, int p) {
// Initialize the count of odd-degree (in T_B) vertices in the subtree rooted at u.
// Starts with 1 if u itself is in O_B, otherwise 0.
subtree_odd_count[u] = is_odd_B[u];
// Iterate through all neighbors of u in the Red Tree T_R.
for (int v : adj_R[u]) {
// Skip the parent node to prevent infinite loops in the undirected graph.
if (v == p) continue;
// Recursively call dfs1 for the child node v.
dfs1(v, u);
// Accumulate the count from the child's subtree into the current node's count.
subtree_odd_count[u] += subtree_odd_count[v];
}
// After visiting all children, consider the edge connecting u to its parent p.
// This check determines if the edge (p, u) is part of the red paths needed for the matching.
// The condition `p != 0` ensures we don't process a dummy edge for the root node (node 1).
// `subtree_odd_count[u] % 2 != 0` checks if the subtree rooted at u contains an odd number of O_B vertices.
// If true, the edge (p, u) must be traversed by exactly one path in the minimum cost matching.
if (p != 0 && subtree_odd_count[u] % 2 != 0) {
// Increment the total cost C(O_B) because this edge contributes 1 unit of length.
C_OB++;
// Add the edge (u, p) to the adjacency list of G'. G' represents the union of paths in the matching.
adj_G_prime[u].push_back(p);
adj_G_prime[p].push_back(u);
}
}
/**
* @brief Second DFS on the forest G'.
* Finds the diameter of each connected component (which is a path).
* Updates the global maximum path length found (`max_path_len`).
*
* @param u Current node being visited.
* @param p Parent node in the DFS traversal within G'.
* @param current_component_max_len Reference variable to store the diameter of the current component being processed.
* @return The depth of the longest path starting from u downwards in its component path.
*/
int dfs2(int u, int p, int& current_component_max_len) {
// Mark the current node as visited to avoid reprocessing.
visited[u] = true;
// Initialize maximum depths for paths starting from u downwards.
int max_depth1 = 0; // Length of the longest path downwards from u.
int max_depth2 = 0; // Length of the second longest path downwards from u (through a different branch, if exists).
// Iterate through neighbors of u in the forest G'.
for (int v : adj_G_prime[u]) {
// Skip the parent node.
if (v == p) continue;
// Recursively call dfs2 for the child node v. The returned depth is from v downwards.
// Add 1 to include the edge (u, v).
int depth = dfs2(v, u, current_component_max_len) + 1;
// Update the two longest path depths starting from u.
if (depth > max_depth1) {
max_depth2 = max_depth1; // Old max_depth1 becomes the second longest.
max_depth1 = depth; // The new depth is the longest.
} else if (depth > max_depth2) {
max_depth2 = depth; // The new depth is the second longest.
}
}
// The diameter of a tree component passing through node u is the sum of the two longest paths starting from u.
// For a path graph, this calculation correctly finds its length (diameter).
// Update the maximum diameter found within the current component.
current_component_max_len = std::max(current_component_max_len, max_depth1 + max_depth2);
// Return the depth of the longest path starting from u downwards. This value is used by the caller (parent node).
return max_depth1;
}
int main() {
// Use fast I/O operations.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of vertices.
std::cin >> N;
// Resize all required vectors to N+1 to use 1-based indexing for vertices.
adj_R.resize(N + 1);
// adj_B is not needed after computing degrees
degree_B.resize(N + 1, 0);
is_odd_B.resize(N + 1, false);
adj_G_prime.resize(N + 1);
subtree_odd_count.resize(N + 1, 0);
visited.resize(N + 1, false);
// Read red edges and build the adjacency list for the Red Tree T_R.
for (int i = 0; i < N - 1; ++i) {
int u, v;
std::cin >> u >> v;
adj_R[u].push_back(v);
adj_R[v].push_back(u);
}
// Read black edges and compute the degree of each vertex in the Black Tree T_B.
for (int i = 0; i < N - 1; ++i) {
int u, v;
std::cin >> u >> v;
degree_B[u]++;
degree_B[v]++;
}
// Identify vertices that have an odd degree in T_B. These vertices form the set O_B.
for (int i = 1; i <= N; ++i) {
if (degree_B[i] % 2 != 0) {
is_odd_B[i] = true;
}
}
// Run the first DFS on T_R starting from an arbitrary root (e.g., vertex 1).
// This computes C(O_B) and builds the graph G'.
dfs1(1, 0);
// Reset the visited flags for the second DFS pass on G'.
visited.assign(N + 1, false);
// Reset the maximum path length found across all components of G'.
max_path_len = 0;
// Iterate through all vertices from 1 to N.
for(int i = 1; i <= N; ++i) {
// Check if vertex i belongs to O_B and has not been visited yet by the second DFS.
// Vertices in O_B are guaranteed to be endpoints (leaves) of paths in the forest G'.
// Starting DFS from an unvisited O_B vertex ensures we process each component exactly once.
if (is_odd_B[i] && !visited[i]) {
// Variable to store the maximum length (diameter) found within this specific component of G'.
int current_component_max_len = 0;
// Run the second DFS starting from this O_B vertex to find the diameter of its component.
dfs2(i, 0, current_component_max_len);
// Update the overall maximum path length found across all components.
max_path_len = std::max(max_path_len, current_component_max_len);
}
}
// Note: Any vertex that is part of G' but not in O_B must be an internal node of some path.
// Such vertices will be visited when the DFS starts from one of the path's endpoints (which are in O_B).
// Therefore, iterating only through O_B vertices is sufficient to find the maximum diameter across all path components.
// Calculate the final minimum total moves required.
// Total moves = (Number of black edges) + (Minimum cost of red edge traversals)
// Minimum cost of red edges = C(O_B) - max_path_len
// Number of black edges = N - 1
long long total_moves = (long long)(N - 1) + C_OB - max_path_len;
std::cout << total_moves << std::endl;
return 0;
}