538E - Demiurges Play Again - CodeForces Solution

///KoJa
#include<bits/stdc++.h>
using namespace std;
#define task "test"
#define vec vector
#define fi first
#define se second
#define BIT(n) (1LL << (n))
#define MASK(x, i) (((x) >> (i))&1)
#define pb push_back
#define mp make_pair
#define SZ(a) (a).begin(), (a).end()
#define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
typedef long long ll;
typedef pair<int, int> ii;

template<class T>
bool maximize(T &a, const T &b) { return ((a < b) ? (a = b, 1) : 0);}
template<class T>
bool minimize(T &a, const T &b) { return ((a > b) ? (a = b, 1) : 0);}
struct Points
{
    ll x, y;
    Points(){}
    Points(ll _x, ll _y)
    {
        x = _x;
        y = _y;
    }
    Points operator - (const Points &other) const { return Points(x - other.x, y - other.y);}
    ll operator * (const Points &other) const { return x * other.y - y * other.x;}
    ll triangle(const Points &b, const Points &c) const {return (*this - b) * (*this - c);}
};
void fastio()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    if(fopen(task ".inp", "r"))
    {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
}
const int N = int(2e5) + 10;
const int INF = 1e9;
int n, dp1[N], dp2[N], cnt[N];
vec<vec<int>> adj(N);
void init()
{
    cin >> n;
    for(int i = 1; i <= n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        adj[x].pb(y);
    }
}
void dfs(int u, bool isMax)
{
    if((int)adj[u].size() == 0)
    {
        dp1[u] = dp2[u] = cnt[u] = 1;
        return;
    }
    for(int v : adj[u])
    {
        dfs(v, isMax^1);
        cnt[u] += cnt[v];
    }
    if(isMax) dp1[u] = -INF;
    else dp2[u] = INF;
    for(int v : adj[u])
    {
        if(isMax)
        {
            dp1[u] = max(dp1[u], cnt[u] - cnt[v] + dp1[v]);
            dp2[u] += dp2[v];
        }
        else
        {
            dp1[u] += (dp1[v] - 1);
            dp2[u] = min(dp2[u], dp2[v]);
        }
    }
    if(!isMax) dp1[u]++;
}
void process(int tc = 0)
{
    dfs(1, 1);
    cout << dp1[1] << " " << dp2[1];
}

int main()
{
    fastio();
    int tc = 1;
    //cin >> tc;
    for(int i = 1; i <= tc; i++)
    {
        init();
        process(i);
    }
    return 0;
}