[ABC246G] Game on Tree 3 题解

· · 题解

前言

解题思路

本题解参照题目翻译，认为移动的一方为 B，另一方为 A。

容易发现答案具有单调性，考虑二分答案。

定义 target 为 B 的目标（二分的答案），并且认为当 B 经过若干次行动后能到达满足 val_i \geq target 的点 i 时 target 为一个满足条件的解，于是我们考虑如何判断 target 是否为解。

为了方便，我们对点进行染色：在 target 已经确定的情况下，定义一个点为黑点当且仅当 val_i \geq target，否则为白点。

定义 f_i 表示当 B 移动到点 i 之前，如果 B 下一步就要移动到点 i，那么 A 至少需要进行多少次操作才能保证 B 在以 i 为根的子树内一定无法到达任何黑点。

通俗易懂的解释是：如果 B 开局的时候下一步就要到达 i，那么 A 至少要作弊额外修改多少个节点的颜色才能使得 B 即使走到根为 i 的子树也走不到任何黑点。

其实不是很直观，如果感觉难以理解建议手玩一下，很好懂的。

接下来考虑转移方程：

f_i=\max(\sum f_j-1,0)+[val_i \geq target]

其中 \sum f_j 为点 i 的所有孩子的 f 值之和。

为什么是对的呢？

当 B 从点 i 开始进行移动，并且点 i 还有子节点 j 能使得 B 走到 j 之后能到达黑点，那么 B 就一定会走这个点。为了避免这种情况，A 必须保证在到达 i 之前至少使用了 \sum f_j-1 次操作以保证 B 走到 i 之后无论选择哪个子树都不能到达黑点（此处要 -1 是因为 B 走到点 i 的回合 A 还能进行一次操作）。

而 [val_i \geq target] 就是判断点 i 是否为黑点，如果是，那么还要在到达 i 之前匀出一次操作来把 i 变为白点。

因为 B 开局就在点 1 上，所以判断对于一个既定的 target 是否有解，只需要进行一次 DP 之后判断 f_1 是否等于 0 即可。

总时间复杂度 O(n\log{a_{max}})，能过。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200100;
long long val[MAXN],n,cpy[MAXN],dp[MAXN];
vector<long long> e[MAXN];
void check(long long x,long long tag,long long fat)
{
    long long i,mp=e[x].size()-1,v,sum=0;
    for(i=0;i<=mp;i++)
    {
        v=e[x][i];
        if(v==fat)
        {
            continue;
        }
        else
        {
            check(v,tag,x);
            sum+=dp[v];//求子节点的和 
        }
    }
    sum=max(sum-1,0ll);//为了避免减到 0 以下 
    dp[x]=sum+(val[x]>=tag);//判断是否为黑点 
    return;
}
int main()
{
    long long i,j,ta,tb,l,r,mid,maxn=0,ans=0;
    scanf("%lld",&n);
    for(i=2;i<=n;i++)
    {
        scanf("%lld",&val[i]);
        cpy[i]=val[i];
        maxn=max(maxn,val[i]);
    }
    for(i=1;i<n;i++)
    {
        scanf("%lld%lld",&ta,&tb);
        e[ta].push_back(tb);
        e[tb].push_back(ta);
    }
    sort(cpy+1,cpy+1+n);
    l=1;
    r=n;
    while(l<=r)//二分答案 
    {
        mid=(l+r)/2;
        check(1,cpy[mid],0);
        if(dp[1]>=1)
        {
            ans=mid;
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    printf("%lld",cpy[ans]);
    return 0;
}