Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct State {
- vector<vector<int>> ady;
- vector<array<int, 2>> dp;
- };
- void solve(State& state, int curr, int parent) {
- auto& dp = state.dp;
- for (auto& a : state.ady[curr]) {
- if (a == parent)
- continue;
- solve(state, a, curr);
- dp[curr][0] += max(dp[a][0], dp[a][1]);
- }
- for (auto& a : state.ady[curr]) {
- if (a == parent)
- continue;
- dp[curr][1] = max(1 + dp[curr][0] - dp[a][1] + dp[a][0], dp[curr][1]);
- }
- }
- int main() {
- int n;
- cin >> n;
- State state;
- state.ady.resize(n + 1);
- state.dp.resize(n + 1, {0, 0});
- for (int i = 0; i < n - 1; i++) {
- int a, b;
- cin >> a >> b;
- state.ady[a].push_back(b);
- state.ady[b].push_back(a);
- }
- solve(state, 1, -1);
- cout << max(state.dp[1][0], state.dp[1][1]) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement