Codeforces 538E - Demiurges Play Again

Problem Statement:
538E - Demiurges Play Again

Solution:

Interesting problem. Although it seems to have large search space, by making use of interesting observations we can solve it in linear time (i.e. visiting each node exactly once).

First focus on trying to get the maximum result. Note that both player play optimally, hence the result of a game is deterministic. Consider a subtree T rooted at v. Let v.size be the number of leaves in T. Furthermore, let v.best be the maximum result obtained by an optimal labelling of leaves of T using label i = 1 .. v.size. We have two cases:
1. First player makes a move at node v. He will then choose a child of v that maximises result. For all w children of v, we check w.size and w.best. Pick the one that gives maximum of v.size - w.size + w.best (i.e. we place the biggest labels on the leaves of subtree rooted at w)
2. Second player makes a move at node v. He will choose a child w that minimises the result. Our job is to make the minimum choice as large as possible. It can be proved that the biggest possible will be \(1 + \sum_{w \text{ child of } v} (w.best - 1) \).



Similar analysis is done to compute the minimum possible arrangement; let v.worst be the worst possible result, then we have 2 cases as well:
1. First player makes a move at node v. To minimise the maximum, it can be shown that the minimum possible will be \( \sum_{w \text{ child of } v} w.worst \).
2. Second player makes a move at node v. We pick the minimum w.worst (i.e. we place the lowest labels in that subtree).

The above computation is done recursively as follows:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct info {
    int size;
    int best;
    int worst;
};

vector<vector<int> > adj;
vector<info> node;
int n;

void dfs(int u, int me) {
    if (adj[u].size() == 0) {
        node[u].size = 1;
        node[u].best = 1;
        node[u].worst = 1;
        return;
    }
    int size = 0;
    for(int i=0;i<adj[u].size();++i){
        int v = adj[u][i];
        dfs(v, me ^ 1);
        size += node[v].size;
    }
    int best = 0;
    int worst = 12345678;
    if (me == 1) {
        worst = 0;
        for(int i=0;i<adj[u].size();++i){
            int v = adj[u][i];
            best = max(best, size - node[v].size + node[v].best);
            worst += node[v].worst;
        }
    } else {
        best = 0;
        for (int i = 0;i < adj[u].size(); ++i){
            int v = adj[u][i];
            best += node[v].best - 1;
            worst = min(worst, node[v].worst);
        }
        best++;
    }
    node[u].size = size;
    node[u].best = best;
    node[u].worst = worst;
}

int main(){
    scanf("%d",&n);
    int u,v;
    adj = vector<vector<int> >(n+3);
    node = vector<info> (n+3);
    for(int i=0;i<n-1;++i){
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
    }
    dfs(1, 1);
    printf("%d %d\n", node[1].best, node[1].worst);
    return 0;
}