题解：P12437 [NERC2023] Fugitive Frenzy

· · 题解

显然的是，A 和 B 都会往叶子走。

对于 B 来说，如果 A 向 B 移动，则如果 B 所在的位置不是叶子，调整为以 A 为根时 B 子树内任意一个叶子显然更优，因此 B 一定会瞬移到叶子节点；对于 A 来说，目的地不是叶子一定抓不到 B。因此两人都往叶子走。

令 f_u 表示 A 初始在 u 的答案，p_{u,v} 表示 A 在结点 u 时前往叶子 B 的概率，q_{u,v} 表示 A 在结点 u 时 B 前往叶子 v 的概率，d_{u,v} 表示树上 u,v 的距离。则容易列出：

f_u=\sum_{v\ne u,v\in \text{leaf}} p_{u,v}(d_{u,v}+f_v(1-q_{u,v}))

根据纳什均衡的结论，A 的策略不论怎样 B 都能得以最大化，因此 d_{u,v}+f_v(1-q_{u,v}) 对于同一个 u 是相等的。

q_{u,v}=1-\dfrac{f_u-d_{u,v}}{f_v} \\ \sum_{v\ne u,v\in \text{leaf}} q_{u,v}=|\text{leaf}|-[u\in \text{leaf}]+\sum_{v\ne u,v\in \text{leaf}}\dfrac{d_{u,v}}{f_v}-f_u\sum_{v\ne u,v\in \text{leaf}}\dfrac{1}{f_v} \\ f_u=\dfrac{|\text{leaf}|-[u\in \text{leaf}]-1+\sum_{v\ne u,v\in \text{leaf}}\dfrac{d_{u,v}}{f_v}}{\sum_{v\ne u,v\in \text{leaf}}\dfrac{1}{f_v}}

与多数期望问题不同，这个式子不是线性方程组的形式，并不好处理。但是由于精度要求有限，可以直接迭代计算。即：令 f_u\gets 1，然后按定义式计算若干轮即可。

void sol(){
    up(i,1,n){
        int sz=leaf.size()-(E[i].size()==1);
        db s1=0,s2=0;for(int p:leaf)if(p^i)s1+=d[i][p]/f[p],s2+=1/f[p];
        g[i]=(s1+sz-1)/s2;
    }
    up(i,1,n)f[i]=g[i];
}