Skip to content

Instantly share code, notes, and snippets.

@HyeonWooKim
Created November 29, 2016 15:27
Show Gist options
  • Save HyeonWooKim/ad4b3118950926342c2e8df17d40bf17 to your computer and use it in GitHub Desktop.
Save HyeonWooKim/ad4b3118950926342c2e8df17d40bf17 to your computer and use it in GitHub Desktop.
BOJ 2533
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
int dp[1000001][2];
bool visited[1000001];
vector<vector<int> >v;
int dfs(int cur, bool adp)
{
int &ret = dp[cur][adp];
if (ret != -1) return ret;
visited[cur] = true;
ret = adp ? 1 : 0;
for (int there : v[cur])
{
if (!visited[there])
{
if(!adp) ret += dfs(there, true);
else ret += min(dfs(there, true), dfs(there, false));
}
}
visited[cur] = false;
return ret;
}
int main()
{
int n;
scanf("%d", &n);
v.resize(n + 1);
for (int i = 0; i < n-1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = -1;
cout << min(dfs(1, true), dfs(1, false));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment