Advertisement
Tarche

tree-matching-tarche

Jun 14th, 2021
746
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct State {
  6.     vector<vector<int>> ady;
  7.     vector<array<int, 2>> dp;
  8. };
  9.  
  10. void solve(State& state, int curr, int parent) {
  11.     auto& dp = state.dp;
  12.  
  13.     for (auto& a : state.ady[curr]) {
  14.         if (a == parent)
  15.             continue;
  16.  
  17.         solve(state, a, curr);
  18.  
  19.         dp[curr][0] += max(dp[a][0], dp[a][1]);
  20.     }
  21.  
  22.     for (auto& a : state.ady[curr]) {
  23.         if (a == parent)
  24.             continue;
  25.         dp[curr][1] = max(1 + dp[curr][0] - dp[a][1] + dp[a][0], dp[curr][1]);
  26.     }
  27. }
  28.  
  29. int main() {
  30.     int n;
  31.     cin >> n;
  32.  
  33.     State state;
  34.     state.ady.resize(n + 1);
  35.     state.dp.resize(n + 1, {0, 0});
  36.  
  37.     for (int i = 0; i < n - 1; i++) {
  38.         int a, b;
  39.         cin >> a >> b;
  40.         state.ady[a].push_back(b);
  41.         state.ady[b].push_back(a);
  42.     }
  43.  
  44.     solve(state, 1, -1);
  45.     cout << max(state.dp[1][0], state.dp[1][1]) << '\n';
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement