游戏

 

Problem

Source: BSOJ 3077

Description

话说前年 Alice 和 Bob 相聚在一起玩游戏后,彼此都很忙,因此很少见面。今年由于为了 NOIP2011 又再次相聚,他们俩还是想比比谁能够收集到最多的石子数量。Alice 将石子分成了 N 堆(编号 $1 \dots N$),并且规定了它们的选取顺序,刚好形成一颗有向树。在游戏过程中,两人从根节点开始,轮流取走石子,当一个人取走节点 $i$ 的石子后,另一个人只能从节点 $i$ 的儿子节点中选取一个。当取到某个叶子时游戏结束,然后两人会比较自己得到的石子数量。已知两人采用的策略不一样,Alice 考虑在让 Bob 取得尽可能少的前提下,自己取的最多;而 Bob 想得是在自己尽可能取得多的前提下,让 Alice 取得最少。在两人都采取最优策略的情况下,请你计算出游戏结束时两人的石子数量。

游戏总是 Alice 先取,保证只存在一组解。

数据范围:

  • 对于 $30\%​$ 的数据,$1\leq N \leq 100​$,$1 \leq \text{num}[i] \leq 100​$

  • 对于 $60\%$ 的数据,$1\leq N\leq 10,000$,$1\leq \text{num}[i]\leq 10,000$

  • 对于 $100\%$ 的数据,$1\leq N\leq 100,000$,$1\leq \text{num}[i]\leq 10,000$

Input

第 1 行只有一个正整数 $N$,表示石子堆数;

第 2 行包含 $N$ 个整数,第 $i$ 个数表示第 $i$ 堆石子的数量 $\text{num}[i]$;

第 $3 \dots N+1$ 行,每行两个正整数 $u$ 和 $v$,表示节点 $u$ 为节点 $v$ 的父亲;

Output

输出文件仅一行为两个整数,分别表示 Alice 取到的石子数和 Bob 取到的石子数。

Sample Input

6 
4 16 16 5 3 1 
1 2 
2 4 
1 3 
3 5 
3 6

Sample Output

7 16

Output Details

首先 Alice 一定能取得节点 1 的 4 个石子,留给 Bob 的是节点 2 和 3,均为 16 个石子。若选取节点 2 则 Alice 下一次可以最多得到 5 个石子,而选择 3,则 Alice 最多也只能得到 3 个石子,所以此时 Bob 会选择节点 3,故 Alice 最后得到的石子数为 7,Bob 为 16。

 

Solution

首先应该对每个点进行染色,根据该点到根的距离,判断出该点是先手取到还是后手取到。然后对该点进行记忆化搜索,根据先后手情况有下面两个计算公式:

$f[i][2]$ 中 $f[i][0]$:节点 $i$ 为子树的博弈中先手能够取到的得分

$f[i][1]$:节点 $i$ 为子树的博弈中后手能够取到的得分

  • 若节点 $i​$ 为 Alice 取得:

      for j ∈ i.child
      if(f[j][0] > f[i][1] || (f[j][0] == f[i][1] && f[j][1] < f[i][0])) { 
          f[i][0] ← f[j][1];
          f[i][1] ← f[j][0];
      }  
      f[i][0] ← f[i][0] + value[i]
    
  • 若节点 $i$ 为 Bob 取得:

      for j ∈ i.child
      if(f[j][1] < f[i][0] || (f[j][1] == f[i][0] && f[j][0] > f[i][1])) {
          f[i][0] ← f[j][1];
          f[i][1] ← f[j][0];
      }
      f[i][0] ← f[i][0] + value[i]
    

最后输出根节点的 $f[root][0]$ 和 $f[root][1]$ 即为答案。

由于数据范围较大,直接 DFS 会爆栈,所以需要使用人工栈,或是从叶节点进行 BFS 反推至根节点。

Code

Github (C++)

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int M = 1000005, inf = 0x7fffffff/2;

struct node {
    int to, next;
} T[M];

int a[M], h[M], vis[M], color[M], ch[M], f[M][2], father[M], q[M];
int cnt, root, n;

void AddEdge(int x, int y) {
    cnt++;
    T[cnt].to = y;
    T[cnt].next = h[x];
    h[x] = cnt;
}

void Dye() {
    int L = 0, R = 1;
    q[R] = root;

    while(L != R) {
        L = (L+1) % M;
        int k = q[L];
        for(int i = h[k]; i; i = T[i].next) {
            int to = T[i].to;
            if(!color[to]) {
                color[to] = 3 - color[k];
                R = (R + 1) % M;
                q[R] = to;
            }
        }
    }
}

void Bfs() {
    int L = 0, R = 0;

    for(int i = 1; i <= n; i++) {
        f[i][0] = inf, f[i][1] = 0;
        if(ch[i] == 0) q[++R] = i, f[i][0] = 0;
    }

    while(L != R) {
        L = (L + 1) % M;
        int v = q[L], u = father[v];
        f[v][0] += a[v];

        if(color[v] == 1) {
            if(f[v][1] < f[u][0] || (f[v][1] == f[u][0] && f[v][0] > f[u][1]))
                f[u][0] = f[v][1], f[u][1] = f[v][0];
        }

        else {
            if(f[v][0] > f[u][1] || (f[v][0] == f[u][1] && f[v][1] < f[u][0]))
                f[u][0] = f[v][1], f[u][1] = f[v][0];
        }

        if(!--ch[u]) {
            R = (R + 1) % M;
            q[R] = u;
        }
    }
}

int main() {
    int u, v;

    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        AddEdge(u, v);
        vis[v] = 1, ch[u]++, father[v] = u;
    }

    for(int i = 1; i <= n; i++)
        if(!vis[i]) {
            root = i;
            break;
        }

    color[root] = 1;

    Dye();
    Bfs();

    printf("%d %d\n", f[root][0], f[root][1]);

    return 0;
}