[CF 538E] Demiurges Play Again

作法：

把題目要求的兩個數值分開計算，兩個數的算法類似，所以這裡只敘述「目的是要讓最終結果越大越好」的那個人的作法。對每個節點 $x$ 紀錄兩個 $dp$ 值，一個代表「若 $x$ 形成的子樹的子節點編號為 $1$ ~ $k$ ，且此時輪到先手，那麼在雙方採取最佳策略後所可以停留的最大值」，令一個則是輪到後手時的最終停留數字的最大值（假設 $dp[ x ][ 0 ]$ 代表前者，$dp[ x ][ 1 ]$ 代表後者）。首先計算 $dp[ x ][ 0 ]$ ，當 x 是葉子的時候顯然是 $1$ 。當 x 不是葉子的時候，假設他的子節點為 $T_1$ ~ $T_k$ ，並且記 $T_i$ 子樹的葉子數為 $S_i$ ，還有記 $d_i = dp[ T_i ][ 1 ]$ （因為走下去之後是輪到後手），那麼首先要先釐清其實 $d_i$ 代表的意義為：如果先手此時決定走向 $T_i$ ，那麼最後就一定會停留在 $T_i$ 的所有葉子中數值第 $d_i$ 小的節點上。因為我們在DP時是假設這棵子樹的葉子是從 $1$ 開始往上編號的，但事實上如果不是的話，也不影響雙方的最佳策略，因為和兩人的決策有關的只有「這個數是否比那個數大」，而不是每個數真正的數值。現在我們有 $1$ ~ $( S_1 + ... + S_k )$ 這些編號，且目的是要找出一個好的編號方法，讓先手做完決策之後最後到的數值最大。而由前面的結論可以知道，如果我們把 $a_1$ ~ $a_{S_i}$ 這些數分到子樹 $T_i$ 裡面的話（其中 $a_i < a_{ i+1 }$），那麼當先手決定走到 $T_i$ 時最終就會停留在 $a_{d_i}$ ，也就是不管在這個子樹裡放哪些數，都會恰好有 $S_i - d_i$ 個比終點還大但沒辦法走到的點，因此為了不讓那些「被浪費掉的大數值太多」，此時的最好配置方法就是：找出所有子樹中 $S_i - d_i$ 最小的子樹，並且把 $1$ ~ $( S_1 + ... + S_k )$ 中最大的 $S_i$ 個數都分配到這個子樹裡，這樣先手就會決定往這個子樹走，最後就會停留在標號 $( S_1 + ... + S_k ) - ( S_i - d_i )$ 的節點。

至於 $dp[ x ][ 1 ]$ 的算法則不太一樣了，因為後手的目的是要讓走到的數越小越好，因此他會去找每個子樹 $T_i$ 所標的所有數值中，第 $d_i$ 小的數最小會是多少，因此我們要找一個好的配置方法，使得後手不管怎麼樣都會選到一個蠻大的數。此時最好的配置方法為：記所有子樹的 $S_i - d_i + 1$ 的總和為 $S$ ，那麼就把 $1$ ~ $( S_1 + ... + S_k )$ 中最大的 $S$ 個數分配到每個子樹的「第 $d_i$ 小到第 $S_i$ 小的數」裡，這樣後手就會選擇走到 $( S_1 + ... + S_k ) - S + 1$ 所在的子樹了，因為這是所有子樹中，第 $d_i$ 小的數的最小值。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
vector<int> v[maxn] ;
int ma[maxn][2] , mi[maxn][2] ; /// 0 : fir , 1 : sec
int num[maxn] ;
void dfs(int x)
{
    if(v[x].empty())
    {
        ma[x][0]=ma[x][1]=mi[x][0]=mi[x][1]=1 ;
        num[x]=1 ; return ;
    }
    for(auto i :v[x]) dfs(i) , num[x]+=num[i] ;
 
    int sum1=0,sum2=0 ;
    mi[x][1]=maxn ;
    for(auto i :v[x])
    {
        ma[x][0]=max(ma[x][0],num[x]-(num[i]-ma[i][1])) ;
        sum1+=num[i]-ma[i][0]+1 ;
        sum2+=mi[i][1] ;
        mi[x][1]=min(mi[x][1],mi[i][0]) ;
    }
    ma[x][1]=num[x]-sum1+1 ;
    mi[x][0]=sum2 ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
    }
    dfs(1) ;
    printf("%d %d\n",ma[1][0],mi[1][0]) ;
}