ABC246G Game on Tree 3 Solution

更好的阅读体验戳此进入

题面

类似于 LG-P3554 [POI2013]LUK-Triumphal arch，给定一棵树，有点权，B 初始在 $1$$1$，每轮 A 选择一个点将权值变为 $0$$0$，然后 B 移动一次，B 可在任意时刻停止游戏然后获得所在点上的权值的得分，两人均采取最优策略那么最终 B 最少会拿到多少的得分。

Solution

与 LG-P3554 [POI2013]LUK-Triumphal arch 基本相同，对于本题依然考虑二分答案，对于当前的答案 $k$$k$，认为树上点权大于 $k$$k$ 的贡献为 $1$$1$，小于等于的为 $0$$0$，于是显然可以树形 DP，令 $dp(i)$$dp(i)$ 表示 A 在 $i$$i$ 节点上时需要额外多少次的变为 $0$$0$ 的操作，显然有转移 $dp(i)=max(\sum _{j\in son(i)}dp(j)-1,0)+[v(i)>k]$$dp(i) = \max(\sum_{j \in son(i)} dp(j) - 1, 0) + \left[ v(i) \gt k \right]$，最后判断一下根节点 $1$$1$ 为 $0$$0$ 则合法，反之不合法。

对于二分的当然可以直接二分值域，不过这里可以考虑一个小剪枝，上界显然为点权的最小值，若根节点有多个子树，那么下界显然为根节点连接的节点的点权的最小值。

Code

88
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template<typename T = int>
24
inline T read(void);
25

26
int N;
27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    OPNEW;
31
}ed[410000];
32
ROPNEW(ed);
33
Edge* head[210000];
34

35
int val[210000];
36
int mnval(INT_MAX), mxval(-1);
37
int f[210000];
38

39
void dfs(int k, int p = 1, int fa = 0){
40
    for(auto i = head[p]; i; i = i->nxt){
41
        if(SON == fa)continue;
42
        dfs(k, SON, p);
43
        f[p] += f[SON];
44
    }
45
    f[p] -= 1;
46
    f[p] = max(0, f[p]);
47
    f[p] += val[p] > k ? 1 : 0;
48
}
49
bool Check(int K){
50
    memset(f, 0, sizeof(f));
51
    dfs(K);
52
    return f[1] == 0;
53
}
54
int main(){
55
    N = read();
56
    for(int i = 2; i <= N; ++i)val[i] = read(), mxval = max(mxval, val[i]);
57
    for(int i = 1; i <= N - 1; ++i){
58
        int s = read(), t = read();
59
        head[s] = new Edge{head[s], t};
60
        head[t] = new Edge{head[t], s};
61
        if(s == 1)mnval = min(mnval, val[t]);
62
        if(t == 1)mnval = min(mnval, val[s]);
63
    }if(!head[1]->nxt)mnval = 0;
64
    int l = mnval, r = mxval;
65
    int ans(-1);
66
    while(l <= r){
67
        int mid = (l + r) >> 1;
68
        Check(mid) ? ans = mid, r = mid - 1 : l = mid + 1;
69
    }printf("%d\n", ans);
70
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71
    return 0;
72
}
73

74
template<typename T>
75
inline T read(void){
76
    T ret(0);
77
    short flag(1);
78
    char c = getchar();
79
    while(c != '-' && !isdigit(c))c = getchar();
80
    if(c == '-')flag = -1, c = getchar();
81
    while(isdigit(c)){
82
        ret *= 10;
83
        ret += int(c - '0');
84
        c = getchar();
85
    }
86
    ret *= flag;
87
    return ret;
88
}

UPD

update-2022_10_21 初稿