[Luogu3554] Poi2013 Triumphal arch

Description

Foreseeable和拿破仑的御用建筑师让·夏格伦在玩游戏

让·夏格伦会玩一个叫“凯旋门”的游戏：现在有一棵n个节点的树，表示一个国家 1号点代表这个国家的首都 这个游戏由两个人一起玩 一个玩家扮演视察国家的国王，另一个扮演建立凯旋门的建筑师 一开始只有首都有凯旋门 国王每次会从当前所在城市移动到一个相

邻的城市 在国王每次移动前，建筑师可以选择国家内任意不超过k个城市建造出凯旋门 如果在任意一个时刻，国王所在的城市没有凯旋门 那么国王会很生气，

扮演建筑师的玩家就输了 如果所有的城市都建立起了凯旋门而国王一直没有走到有凯旋门的城市，那么建筑师就胜利了 Foreseeable不会建筑，所以他扮演国王 而让·夏格伦则

“扮演”建筑师（他本来就是建筑师不需要扮演）  容易发现k的大小非常影响游戏有趣度…… 如果k太大，那么建筑师可以在国王行动前就在所有城市建出凯旋门，那么国王就没有胜利的希望了

，这样Foreseeable会掀桌不玩 如果k太小，那么Foreseeable很有可能会发挥自己所剩无几的智商走到一个没有凯旋门的地方  让·夏格伦想享受虐Foreseeable的快感 所以你要帮他确

定最小的k，使得在这个游戏中，如果建筑师足够聪明的话，建筑师必胜

Input 第一行一个整数n 接下来n-1行，每行两个整数u,v，表示u,v相邻 Output 一行一个整数表示最小的k

Sample Input

7 1 2 1 3 2 5 2 6 7 2 4 1

 Sample Output

 3

Hint 1<=n<=300000

样例解释：在foreseeable第一次行动前，让在2,3,4城市建好

凯旋门，然后接下来无论foreseeable走到哪个城市，

在5,6,7建好凯旋门就能保证让的胜利了


答案满足单调性显然可以二分答案，但是二分完之后该如何呢？
直接模拟显然不行...然后就被卡住了。
看了题解。
要跑路的人一定是从根跑到叶子节点，不会回头，因为往回走不但不会逃离，反而会让另一个人染更多的格子，因为他从根节点到这的路径一定都被染过色了。
这为树形DP提供了基础。
我们设 $f[i]$ 为以i为根的子树，要让B不会走到不被染色的节点的子树的最小需要被覆盖数量。
显然 $f[x]=min \left ( \sum_{y\subseteq son[x]} { } f[y] + deg[x] - mid, 0 \right )$ .
$deg[x]$ 为x节点的度数-1(因为不包括他父亲)。
然后最后判断$f[0]$是否等于0就行了。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <map>

using namespace std;

#define reg register

inline char gc() {

    static const int BS =  << ;

    static unsigned char Buf[BS], *st, *ed;

    if (st == ed) ed = Buf + fread(st = Buf, , BS, stdin);

    return st == ed ? EOF : *st++;

}

#define gc getchar

inline int read() {

    int res=;char ch=getchar();bool fu=;

    while(!isdigit(ch)) {if(ch=='-')fu=;ch=getchar();}

    while(isdigit(ch))res=(res<<)+(res<<)+(ch^), ch=getchar();

    return fu?-res:res;

}

#define N 300005

int n;

struct edge {

    int nxt, to;

}ed[N*];

int head[N], cnt, deg[N];

inline void add(int x, int y) {

    ed[++cnt] = (edge){head[x], y};

    head[x] = cnt;

    deg[y]++;

}

int f[N];

int mid;

void dp(int x, int fa)

{

    int res = ;

    for (reg int i = head[x] ; i ; i = ed[i].nxt)

    {

        int to = ed[i].to;

        if (to == fa) continue;

        dp(to, x);

        res += f[to] + ;

    }

    f[x] = max(res - mid, );

}

inline bool check()

{

    memset(f, , sizeof f);

    dp(, );

    return f[] == ;

}

int main()

{

    n = read();

    for (reg int i =  ; i < n ; i ++)

    {

        int x = read(), y = read();

        add(x, y), add(y, x);

    }

    if (n == ) return puts(""), ;

    int l = , r = n, ans;

    while(l <= r)

    {

        mid = l + r >> ;

        if (check()) ans = mid, r = mid - ;

        else l = mid + ;

    }

    cout << ans << endl;

    return ;

}

巴特西

[Luogu3554] Poi2013 Triumphal arch

Description

最新文章

热门文章