来源
在省选模拟赛中读错了 T2 的题面，于是得到了一道比原题简单很多的题。
题目描述
给定一颗 \(n\) 个点的树和一个结束节点 \(w\)。
设当前所在点为 \(u\)，定义一次移动过程如下：
- 在 \(1\) 到 \(n\) 中随机一个点，记作 \(v\)。
- 沿着从 \(u\) 到 \(v\) 的唯一简单路径移动一步，特别地，如果 \(u=v\) 则不移动。
当移动到 \(w\) 时，停止移动。
令 \(E(i)\) 为从 \(i\) 开始移动直到到达 \(w\) 的期望步数（对 \(10^9+7\) 取模）。
求 \(\sum\limits_{i=1}^{n}{E(i) \operatorname{xor} i}\)。
数据范围
\(1 \leq w \leq n \leq 10^6\)。
解法
对于叶节点：
\[E_i = \frac{n-1}{n}E_{fa_i} + \frac{1}{n}E_i + 1\\
E_i = E_{fa_i} + \frac{n}{n-1}\\
f_i = 1\\
g_i = \frac{n}{n-1}\\
\]
对于非叶节点：
\[E_i = 1 + \frac{1}{n}E_i + \frac{n-sz_i}{n}E_{fa_i} + \sum\limits_{j\in son_i}{\frac{sz_j}{n}E_j}\\
E_i = 1 + \frac{1}{n}E_i + \frac{n-sz_i}{n}E_{fa_i} + \sum\limits_{j\in son_i}{\frac{sz_j}{n}(f_jE_i + g_j)}\\
(\frac{n-1}{n} - \sum\limits_{j\in son_i}{\frac{sz_jf_j}{n}})E_i - 1 - \sum\limits_{j\in son_i}{\frac{sz_jg_j}{n}} = \frac{n-sz_i}{n}E_{fa_i}\\
\]
令：
\[p = \frac{n-1}{n} - \sum\limits_{j\in son_i}{\frac{sz_jf_j}{n}}\\
q = 1 + \sum\limits_{j\in son_i}{\frac{sz_jg_j}{n}}\\
r = \frac{n-sz_i}{n}\\
\]
带入可得：
\[pE_i - q = rE_{fa_i}\\
E_i = \frac{r}{p}E_{fa_i} + \frac{q}{p}\\
f_i = \frac{r}{p}\\
g_i = \frac{q}{p}\\
\]
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
const int MOD=1e9+7;
void exgcd(int a,int &x,int b,int &y){
if(!b){
x=1;
y=0;
}else{
exgcd(b,y,a%b,x);
y-=a/b*x;
}
}
int Inv(int x){
int res,y;
exgcd(x,res,MOD,y);
return (res%MOD+MOD)%MOD;
}
int Add(int a,int b){
return a+b>=MOD?a+b-MOD:a+b;
}
int Sub(int a,int b){
return a-b<0?a-b+MOD:a-b;
}
int Mul(int a,int b){
return 1ll*a*b%MOD;
}
int Div(int a,int b){
return 1ll*a*Inv(b)%MOD;
}
int n,w,gleaf,inn,sz[N],f[N],g[N],E[N];
int id,h[N],e[2*N],ne[2*N];
bool vis[N];
ll ans;
void add(int a,int b){
id++;
ne[id]=h[a];
h[a]=id;
e[id]=b;
}
void dfs1(int x){
vector<int> son;
vis[x]=1;
for(int i=h[x];i;i=ne[i]){
if(!vis[e[i]]){
son.push_back(e[i]);
dfs1(e[i]);
sz[x]+=sz[e[i]];
}
}
sz[x]++;
if(sz[x]==1){
f[x]=1;
g[x]=gleaf;
}else{
int p=Sub(1,inn),q=1;
for(int i=0;i<(int)son.size();i++){
p=Sub(p,Mul(Mul(sz[son[i]],f[son[i]]),inn));
q=Add(q,Mul(Mul(sz[son[i]],g[son[i]]),inn));
}
f[x]=Div(n-sz[x],Mul(p,n));
g[x]=Div(q,p);
}
}
void dfs2(int x){
vis[x]=1;
for(int i=h[x];i;i=ne[i]){
if(!vis[e[i]]){
E[e[i]]=Add(Mul(f[e[i]],E[x]),g[e[i]]);
dfs2(e[i]);
}
}
}
int main(){
scanf("%d",&n);
inn=Inv(n);
gleaf=Div(n,n-1);
for(int i=2;i<=n;i++){
int fp;
scanf("%d",&fp);
add(fp,i);
add(i,fp);
}
scanf("%d",&w);
dfs1(w);
memset(vis,0,sizeof(vis));
dfs2(w);
for(int i=1;i<=n;i++){
ans+=E[i]^i;
}
printf("%lld",ans);
return 0;
}