fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /**
  5.  * PROBLEM: Tree Perfect Matching
  6.  * 
  7.  * Given a tree, for each node, check if its subtree can be perfectly paired.
  8.  * 
  9.  * "Perfectly paired" means:
  10.  * - Every node matches with exactly one other node
  11.  * - Matched nodes must be connected by an edge
  12.  * 
  13.  * IMPORTANT ASSUMPTION:
  14.  * - This solution roots the tree at node 0 (after converting to 0-based indexing)
  15.  * - "Subtree of node u" means the subtree when viewing the tree rooted at 0
  16.  * - If the problem specifies a different root, you must change the root node!
  17.  * 
  18.  * Example:
  19.  *     0
  20.  *    / \
  21.  *   1   2
  22.  * 
  23.  * Subtree at 0: {0,1,2} - node 0 pairs with 1, but 2 is alone -> NO
  24.  * We need even nodes AND valid pairing structure
  25.  */
  26.  
  27. int main() {
  28.     ios::sync_with_stdio(false);
  29.     cin.tie(nullptr);
  30.  
  31.     // Read tree size
  32.     int n;
  33.     if (!(cin >> n)) return 0;
  34.  
  35.     // ============================================================
  36.     // Read edges and detect if nodes start from 0 or 1
  37.     // ============================================================
  38.  
  39.     vector<pair<int, int>> edges;
  40.     int min_node = INT_MAX;
  41.     int max_node = INT_MIN;
  42.  
  43.     for (int i = 0; i < n - 1; i++) {
  44.         int a, b;
  45.         cin >> a >> b;
  46.         edges.push_back({a, b});
  47.  
  48.         min_node = min({min_node, a, b});
  49.         max_node = max({max_node, a, b});
  50.     }
  51.  
  52.     // Improved indexing detection:
  53.     // - If max_node == n, definitely 1-based (n is invalid in 0-based)
  54.     // - If min_node == 1 and max_node == n, definitely 1-based
  55.     // - If min_node == 0, definitely 0-based
  56.     bool starts_from_one = (max_node == n) || (min_node == 1 && max_node == n);
  57.  
  58.     // ============================================================
  59.     // Build the tree (convert to 0-based indexing)
  60.     // ============================================================
  61.  
  62.     vector<vector<int>> tree(n);
  63.  
  64.     for (auto [a, b] : edges) {
  65.         // Convert to 0-based if needed
  66.         if (starts_from_one) {
  67.             a--;
  68.             b--;
  69.         }
  70.  
  71.         // Validate indices after conversion
  72.         if (a < 0 || a >= n || b < 0 || b >= n) {
  73.             return 0;  // Invalid input
  74.         }
  75.  
  76.         tree[a].push_back(b);
  77.         tree[b].push_back(a);
  78.     }
  79.  
  80.     // ============================================================
  81.     // Root the tree at node 0
  82.     // ============================================================
  83.     // NOTE: If the problem specifies a different root, change this!
  84.  
  85.     const int ROOT = 0;
  86.  
  87.     vector<int> parent(n, -1);
  88.     vector<int> nodes;  // All nodes in visit order
  89.  
  90.     // Use DFS to establish parent-child relationships
  91.     stack<int> s;
  92.     s.push(ROOT);
  93.     parent[ROOT] = ROOT;  // Root is its own parent
  94.  
  95.     while (!s.empty()) {
  96.         int node = s.top();
  97.         s.pop();
  98.         nodes.push_back(node);
  99.  
  100.         for (int next : tree[node]) {
  101.             if (parent[next] == -1) {  // Not visited yet
  102.                 parent[next] = node;
  103.                 s.push(next);
  104.             }
  105.         }
  106.     }
  107.  
  108.     // Build list of children for each node
  109.     vector<vector<int>> kids(n);
  110.     for (int i = 0; i < n; i++) {
  111.         if (i != ROOT && parent[i] >= 0) {
  112.             kids[parent[i]].push_back(i);
  113.         }
  114.     }
  115.  
  116.     // ============================================================
  117.     // Solve with Dynamic Programming
  118.     // ============================================================
  119.  
  120.     /**
  121.      * Two states for each node:
  122.      * 
  123.      * paired[node] = 1 if subtree can be matched with this node 
  124.      *                paired to one of its kids
  125.      * 
  126.      * alone[node] = 1 if subtree can be matched leaving this node 
  127.      *               free (to pair with parent later)
  128.      * 
  129.      * Note: Using vector<char> instead of vector<bool> for performance
  130.      * (vector<bool> is a specialized bitset that can be slower)
  131.      */
  132.  
  133.     vector<char> paired(n, 0);
  134.     vector<char> alone(n, 0);
  135.  
  136.     // Process from bottom to top (kids before parents)
  137.     reverse(nodes.begin(), nodes.end());
  138.  
  139.     for (int node : nodes) {
  140.         int num_kids = kids[node].size();
  141.  
  142.         // --------------------------------------------------------
  143.         // Can this node be left alone?
  144.         // --------------------------------------------------------
  145.         // Yes, if ALL kids are paired within their own subtrees
  146.  
  147.         alone[node] = 1;
  148.         for (int kid : kids[node]) {
  149.             if (!paired[kid]) {
  150.                 alone[node] = 0;
  151.                 break;
  152.             }
  153.         }
  154.  
  155.         // --------------------------------------------------------
  156.         // Can this node pair with a kid?
  157.         // --------------------------------------------------------
  158.         // Yes, if we can find ONE kid to pair with, and all 
  159.         // OTHER kids are paired in their subtrees
  160.  
  161.         if (num_kids == 0) {
  162.             // Leaf - no kids to pair with
  163.             paired[node] = 0;
  164.         } else {
  165.             // Try pairing with each kid
  166.             // Use prefix/suffix to quickly check "all others paired"
  167.  
  168.             // before[i] = are all kids with index < i paired?
  169.             // after[i]  = are all kids with index > i paired?
  170.             vector<char> before(num_kids + 1, 1);
  171.             vector<char> after(num_kids + 1, 1);
  172.  
  173.             for (int i = 0; i < num_kids; i++) {
  174.                 before[i + 1] = before[i] && paired[kids[node][i]];
  175.             }
  176.  
  177.             for (int i = num_kids - 1; i >= 0; i--) {
  178.                 after[i] = after[i + 1] && paired[kids[node][i]];
  179.             }
  180.  
  181.             // Check each kid as a potential partner
  182.             paired[node] = 0;
  183.             for (int i = 0; i < num_kids; i++) {
  184.                 int kid = kids[node][i];
  185.  
  186.                 // Can we pair this node with this kid?
  187.                 // Requirements:
  188.                 // 1. Kid must be alone (available to pair with parent)
  189.                 // 2. All other kids must be paired in their subtrees
  190.                 if (alone[kid] && before[i] && after[i + 1]) {
  191.                     paired[node] = 1;
  192.                     break;  // Found a valid pairing!
  193.                 }
  194.             }
  195.         }
  196.     }
  197.  
  198.     // ============================================================
  199.     // Output the answer
  200.     // ============================================================
  201.  
  202.     // For each node i, the answer is whether its subtree can be paired
  203.     // Since node i is the ROOT of its subtree, we use paired[i]
  204.     // (The root cannot be paired upward to a parent)
  205.  
  206.     string result(n, '0');
  207.     for (int i = 0; i < n; i++) {
  208.         result[i] = paired[i] ? '1' : '0';
  209.     }
  210.  
  211.     cout << result << "\n";
  212.  
  213.     return 0;
  214. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bHZGf1
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!