题解：CF2028E Alice's Adventures in the Rabbit Hole

Mr_Terminator · 2024-11-22 10:20:10 · 题解

记这棵树是一个以 1 号点为根的有根树。这题首先需要得到的一个性质是：Alice 每次操作必须要往父亲方向走，Queen 每次操作一定要把 Alice 往远离父亲的方向拖。

为什么呢？首先，在一个非根节点，Alice 如果想活必须会经过自己父亲。如果自己获得了操作机会却往下走，还得再回来、往上走，依旧会经过父亲。于是，一个简单的结论出来了：

Alice 的存活概率必然不高于在父亲节点的存活概率。

其次，Queen 知道了这个结论。由于 Queen 想要处决 Alice，那么轮到她操作的时候，不可能把 Alice 往父亲拖，因为这样只会增加 Alice 的存活概率。

这样，一个最基本的想法便出现了：

记 f_i 为当前 Alice 在 i 号点的生存概率，那么：

• 如果 i=1，则 f_i=1。

• 否则，如果 i 是叶子，则 f_i=0。

• 再否则，设 fa_{i} 为 i 的父亲，S_{i} 为 i 的儿子构成的集合，则 f_{i}=\frac{1}{2}f_{fa_{i}}+\frac{1}{2}\min\limits_{s\in S_{i}}f_{s}——其中两个 \frac{1}{2} 后面的式子分别表示 Alice 和 Queen 决策后 Alice 的胜率。

于是我们遇到了一个致命的问题：这个 \min 拆不了了。

正在我们百思不得其解的时候，我们重温了前面的结论的一句话：

Alice 每次操作必须要往父亲方向走。

我们又得到了灵感：如果 Alice 初始在 i 号点，她要存活，首先要爬到 fa_{i}。如果没有爬到，那她就在 i 号点的子树里面被处决了。爬到 fa_{i} 后，状态就变成“Alice 在 fa_{i} 号点”了。

我们设 g_{i} 为 Alice 从 i 号点出发，能够爬到 fa_{i} 的概率。

• 如果 i 是叶子，则 g_{i}=0，因为 Alice 已经被处决了。

• 否则，如果当前是 Queen 的回合，那么 Queen 肯定会把 Alice 往 g 最小的儿子拖。Alice 当前有 \frac{1}{2} 的概率轮到她的回合，爬到父亲。除此之外，有 \frac{1}{2}\min\limits_{s\in S_{i}}g_{s} 被 Queen 拖走，但是重新回到了 i，剩下的概率就是被拖走处决。自行用等比数列求和推推，发现 g_{i}=\frac{\frac{1}{2}}{1-\frac{1}{2}\min\limits_{s\in S_{i}}g_{s}}=\frac{1}{2-\min\limits_{s\in S_{i}}g_{s}}。

我们发现，现在可以使用一遍深搜求出每一个 g 值，再使用一遍深搜求出答案。本着“期望分步走，一步一期望”的思想，i 号点的胜率就是到根节点路上（不含根，含 i）的节点的所有 g 值之积。

但真的有这么简单吗？

我们回去看了一眼输出精度——这不对啊，这题是模 998244353 输出，那么怎么对一些分数求 \min？

万幸的是，我们及时观察到，任何一个 g 值都可以表示成 1-\frac{1}{X+1}，其中 X 是自然数。我们设 h_i 满足 g_{i}=1-\frac{1}{h_{i}+1}，那么：

• 如果 i 是叶子，则 h_{i}=0。

• 否则，g_{i}=\frac{1}{2-\min\limits_{s\in S_{i}}g_{s}}=\frac{1}{2-\min\limits_{s\in S_{i}}(1-\frac{1}{h_{s}+1})}=\frac{1}{1+\max\limits_{s\in S_{i}}\frac{1}{h_{s}+1}}=\frac{1}{1+\frac{1}{1+\min\limits_{s\in S_{i}}h_{s}}}=1-\frac{1}{1+\min\limits_{s\in S_{i}}h_{s}}，故 h_{i}=1+\min\limits_{s\in S_{i}}h_s。

于是，我们就打破了比较分数的障碍，在最初线性预处理逆元即可。时间复杂度 O(\sum n)，结束。

这题不看题解、从头想一遍确实挺有难度的，但看题解就失去那味了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int T,n,ni[200005],dp[200005],ans[200005];
vector<int>mp[200005];
const int modp=998244353;

void dfs(int now,int fa){
    bool satis=0;
    for(auto nxt:mp[now]){
        if(nxt==fa)continue;
        satis=1;dfs(nxt,now);dp[now]=min(dp[now],dp[nxt]+1);
    }
    if(!satis)dp[now]=0;
}

void dfsEX(int now,int fa){
    for(auto nxt:mp[now]){
        if(nxt==fa)continue;
        ans[nxt]=ans[now]*dp[nxt]%modp*ni[dp[nxt]+1]%modp;
        dfsEX(nxt,now);
    }
}

signed main(){
    cin>>T;ni[1]=1;
    for(int i=2;i<=200004;i++)ni[i]=(modp-modp/i)*ni[modp%i]%modp;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            dp[i]=i==1?0:n+1;mp[i].clear();
        }
        for(int i=1;i<n;i++){
            int xx,yy;cin>>xx>>yy;
            mp[xx].push_back(yy);
            mp[yy].push_back(xx);
        }
        dfs(1,1);ans[1]=1;dfsEX(1,1);
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}