题解：P16338 「ALFR Round 10」纸牌

wangyuel · 2026-04-19 18:01:45 · 题解

可以看出，作为其他玩家，只要将 k 提升到能到达的最大值，就可以尽可能地让主人公输。

明显地，从 p_1 到 p_m，能达到的最大的 k 就是 a_{p_1} 到 a_{p_m} 的最大值。想达到这个值也很简单，直接让除了 a_i 最大的人以外的所有人都选第二种行动，只有最大者选第一种即可。

贪心地，让主人公尽量延后行动一定不劣。我们可以以 d 为根建树，这样对于每个 u，总是先将 u 的子树遍历完，再从 u 向 d 走就能让主人公延后行动。可以看出，此时能达到的 k 值就是 u 的最远的非 d 的祖先，他的子树中 a_i 的最大值。

那就简单了，对于每个节点，维护它的子树中 a_i 的的最大值，然后对于 d 的每个儿子，如果这个儿子能够产生比 a_d 大的 k，则这个儿子及其所有的子节点都可以作为可能的 u。

最后不要忘记特判：如果 b_d>2，那主人公即使弃牌也获胜。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int t, n, d;
int a[N], b[N];
int fa[N], mx[N], sz[N];
vector<int>e[N];
void make_tree(int s){
    mx[s] = a[s];
    sz[s] = 1;
    for(int i : e[s]){
        if(fa[i] == -1){
            fa[i] = s;
            make_tree(i);
            mx[s] = max(mx[s], mx[i]);
            sz[s] += sz[i];
        }
    }
//  printf("node %d: mx %d, sz %d\n", s, mx[s], sz[s]);
}
signed main()
{
    memset(fa, -1, sizeof fa);
    cin >>t;
    while(t--){
        //清空 
        for(int i=1; i<=n; i++){
            e[i].clear();
            fa[i] = -1;
        }
        //输入 
        cin >>n >>d;
        for(int i=1; i<=n; i++) cin >>a[i] >>b[i];
        for(int i=1; i<n; i++){
            int u, v;
            cin >>u >>v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        //特判
        if(b[d] > 2){
            puts("0");
            continue;
        } 
        //建树并预处理
        fa[d] = 0;
        make_tree(d);
        //答案
        int ans = 0;
        for(int son : e[d])
            if(mx[son] >= a[d])
                ans += sz[son];
        cout <<ans <<endl;
    }
    return 0;
}

AC 记录