P7443 「EZEC-7」加边 题解

发布于 2021-03-23  372 次阅读


题意

题目链接

树上的棋子博弈,每个点有权值。你可以添加一条边以试图反败为胜,不同的加边方法根据权值有一个代价,需要最小化这个代价。

解析

我们首先定义一个结点先手必败是 lose,先手必胜是 win,容易发现,叶子结点一定是 ​lose,然后对于每一个非叶子结点,只要它有一个儿子是 ​lose,它就是 win,否则,该结点也是 lose。一遍 dfs 可以求出每一个点的初始状态,从而判断是否输出零。

对于输出非零的情况,我们发现对于这棵尚未加边的树,从起点开始走的话,win 结点一定是对方会走,且会走向一个 lose 结点,而 lose 结点时我们在走。我们考虑怎么连边。显然,我们会从一个 lose 结点向外连边,因为 win​ 结点是对方在走,连了边是没意义的。

接着我们发现,我们一定不会连一条返祖边。因为我们连了返祖边之后,如果走到一个 win 结点,就是对方在走,我们没有办法胜利,如果连到一个 lose​ 结点,那么就使对方变成了我们在那个点时的状态,这样对方走到连出边的这个结点时又可以通过返祖边走到祖先,游戏永远也不会结束。

因此,在放弃了返祖边之后,我们连完一条边后,肯定仍然是一张 DAG(虽然不是树了),显然的,我们只需要连向一条 lose​ 边,并走到那条边,就可以获胜。

接着考虑怎么使代价最小。我们从 $1$ 号点开始 dfs,dfs 时我们走到若干个点,如果是一个 lose 点,那么就是我们走,我们将他试图连向非祖点中权值最小的那个,并更新答案;如果是一个 win 点,那么是对方在走,首先他肯定不会向 win 点走,然后我们观察这个点的儿子中有几个 lose 点,如果有至少两个,那就不用继续 dfs 下去了,因为我们在这个点后面操作一定输,无论我们怎么加边,他都可以选择走子树中没有加边的那个 lose 点。如果儿子中只有一个 lose 点,那么我们走那个点就可以了。

接着又出现了一个问题,我们怎么维护非祖点中权值最小的那个?dead_X 说可以两遍 dfs 或 ST 表,但是我并不会两遍 dfs ,也不想写 ST 表。于是我用了另一种维护方法:第一遍 dfs 时,我们将每一个 lose 点添加到优先队列中,第二遍 dfs 时,我们每 dfs 到一个点,就将这个点标记一下,然后我们弹出优先队列队首的若干个标记过的元素,再取弹出后的队首,这个元素就是我们要找的非祖点中权值最小的那个点,然后再 dfs 结束时,我们将标记取消,且由于这个点可能被弹出了,我们索性:如果这个点是 lose 的话,就再次把这个点扔进优先队列里去。

容易发现这个算法复杂度是 $O(n\log n)$ 的,但是并跑不满,因此通过这题不成问题。

代码

#include<bits/stdc++.h>
#define int long long
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N=2e5+5;
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {//快读
    r=0;bool w=0; char ch=getchar();
    while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
    r=w?-r:r;
}
int T,n,t,A,B,a[N];
struct edge{
    int to,nxt;
}e[N<<1];
int head[N],cnt,fl[N];//1=win 0=lose
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
struct node{
    int id,val;
    bool operator<(const node &x)const{
        return x.val<val;
    }
};
priority_queue<node> q;
bool vis[N];
inline void dfs1(int u){//dfs1 判断初始状态
    fl[u]=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        dfs1(v);if(!fl[v]) fl[u]=1;
    }
    if(!fl[u]) q.push((node){u,a[u]});
}
int ans;
inline void dfs2(int u){
    vis[u]=1;//标记一下
    if(fl[u]==0){//lose 点,自己走
        while(!q.empty()&&vis[q.top().id]) q.pop();
        if(q.empty()){//没有可以用的点了就退出
            vis[u]=0;
            if(!fl[u]) q.push((node){u,a[u]});
            return;
        }
        ans=min(ans,A*a[u]+B*a[q.top().id]);
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;dfs2(v);
        }
    }
    else{//win 点,对方走
        int CNT=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(fl[v]) continue;
            CNT++;
        }
        if(CNT>=2) return;//有两个 lose 儿子,退出
        for(int i=head[u];i;i=e[i].nxt){//仅有一个 lose 儿子,走
            int v=e[i].to;
            if(fl[v]) continue;dfs2(v);
        }
    }
    vis[u]=0;//撤销标记
    if(!fl[u]) q.push((node){u,a[u]});//这个点处理完了再加回去
}
signed main(){
    read(T);
    while(T--){
        while(!q.empty()) q.pop();
        read(n);read(t);read(A);read(B);cnt=0;ans=2e18+5;
        for(int i=1;i<=n;i++) head[i]=0;
        for(int i=1;i<=n;i++) vis[i]=0;
        for(int i=2,x;i<=n;i++){
            read(x);add(x,i);
        }
        for(int i=1;i<=n;i++){
            read(a[i]);
        }
        dfs1(1);
        if(t==0){
            if(fl[1]==1){//初始就能赢
                printf("0\n");continue;
            }
            dfs2(1);
            if(ans==2e18+5) printf("-1\n");//ans 没有可以更新的,输出 -1
            else printf("%lld\n",ans);
        }
        else{
            if(fl[1]==0){
                printf("0\n");continue;
            }
            dfs2(1);
            if(ans==2e18+5) printf("-1\n");
            else printf("%lld\n",ans);
        }
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣