【BZOJ 4169】 4169: Lmc的游戲 （樹形DP）

4169: Lmc的游戲

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?44??Solved:?25

Description

RHL有一天看到lmc在玩一個游戲。

"愚蠢的人類喲，what are you doing"，RHL說。

"我在玩一個游戲。現在這里有一個有n個結點的有根樹，其中有m個葉子結點。這m個葉子從1到m分別被給予了一個

號碼，每個葉子的號碼都是獨一無二的。一開始根節點有一個棋子，兩個玩家每次行動將棋子移動到當前節點的一

個兒子節點。當棋子被移動到某個葉節點的時候游戲結束，這個葉節點的號碼即為該局游戲的result。先手的玩家

要最大化result，后手的玩家要最小化這個result。"

"你不先問一下我是誰嗎 = ="

"那么，who are you"

"我是這個世界的創造者，維護者和毀滅者，整個宇宙的主宰，無所不知，無所不能的，三個字母都大寫的RHL。"

"既然你這么厲害，那你一定知道，在兩個玩家都無限聰明的情況下，在樹的形態已知的情況下，在葉子的編號可

以任意安排的情況下，游戲的result最大是多少咯。"

Input

輸入數據第一行有一個正整數n，表示結點的數量。n<=200000

接下來n-1行，每行有兩個正整數u和v，表示的父親節點是u。

Output

輸出一行2個非負整數，分別表示result的最大值和最小值。

Sample Input

5
1 2
1 3
2 4
2 5

Sample Output

3 2
【樣例解釋】
有3,4,5三個葉子。若令3號葉子的編號是3，則先手可以移到3號結點，故result最大是3。若3號葉子的編號是2，
則先手可以移到3號結點，故result最小是2.

HINT

Source

【分析】

【想出來了】

然而網上沒有題解，我就寫寫，好少人做這題。

如果你是先手的話，你肯定選子樹里面能得到答案最大的那個走。

如果你是后手的話，你肯定選子樹里面能得到答案最小的那個走。

$mx[i]$表示走$i$這棵子樹，$result$最大是多少（指的是，你在子樹填入$a1<a2<a3...$最大是排名第幾的，下同）。

$mn[i]$表示走$i$這棵子樹，$result$最小是多少。

當你是偶數層（$root$這層視為0），即先手操作，你應該是$result=max（子樹1，子樹2，子樹3....)$

最大化$result$顯然是讓各子樹的$result$都最大化，然后呢，因為你取的是$max$，所以最好就是把其他子樹都堆在前面，然后讓$mx$最大的子樹放在最后。

即$mx[x]=max(mx[x],sm[x]-(sm[y]-mx[y]))$; （sm是子樹里面的葉子節點個數）

最小化$result$就是讓子樹都先選$1~mn$放在前面，即$mn[x]+=mn[y]$;

其實解題本質，就是你自己想想怎么樣分配最好嘛。。

當$dep$為奇數，是$result=min(max(),max(),...)$這樣的形式如下

$mx[x]=\sum (mx[y]-1) +1$;

　　$mn[x]=min(mn[x],mn[y])$;

?

　　也不知道怎么說。。

?

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0xfffffff
#define Maxn 200010

int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}

int mx[Maxn],mn[Maxn];

struct node
{
    int x,y,next;
}t[Maxn];
int first[Maxn],len;
void ins(int x,int y)
{
    t[++len].x=x;t[len].y=y;
    t[len].next=first[x];first[x]=len;
}

int sm[Maxn];
void dfs(int x,int dep)
{
    sm[x]=0;
    if(first[x]==0) 
    {
        sm[x]=1;
        mn[x]=mx[x]=1;return;
    }
    for(int i=first[x];i;i=t[i].next)
    {
        int y=t[i].y;
        dfs(y,dep^1);
        sm[x]+=sm[y];
    }
    mx[x]=0;mn[x]=0;
    if(dep) mx[x]=1,mn[x]=INF;
    for(int i=first[x];i;i=t[i].next)
    {
        int y=t[i].y;
        if(!dep)
        {
            mx[x]=mymax(mx[x],sm[x]-(sm[y]-mx[y]));
            mn[x]+=mn[y];
        }
        else
        {
            mx[x]+=mx[y]-1;
            mn[x]=mymin(mn[x],mn[y]);
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int rt=0;
    for(int i=1;i<=n;i++) rt+=i;
    len=0;
    memset(first,0,sizeof(first));
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ins(x,y);
        rt-=y;
    }
    dfs(rt,0);
    printf("%d %d\n",mx[rt],mn[rt]);
    return 0;
}

?