Beauty of tree
题目链接
题目简介
一个有根树，现在有两个人以不同的步长（A和B）分别随机选择树上的一个节点向根的方向遍历这个树， 定义这个树的权重为两个人期望遍历到的所有节点数量之和(如果两个人同时遍历到一个节点，那么这个节点只会计算一次)，求这个树的权重。
解题思路
（借鉴了榜上第二名大佬的代码和思路）
如果直接暴力计算n*n种情况，test set 1是可以通过的。（实测）但是要想通过 test set 2 ,我们还要考虑一些技巧，如果我们认真研究的话，这道题是和概率论紧密相连的。假设题中两个人为 a b , 他们随机选择节点的过程是独立的，当选择的初始节点确定时，所有遍历到的节点就会确定，因此对于某一个节点，设 a 遍历到这个节点的概率为
P
a
P_a
Pa，b 遍历到这个节点的概率为
P
b
P_b
Pb , 那么这个节点被遍历到的概率便是
P
a
+
P
b
−
P
a
∗
P
b
P_a+P_b-P_a*P_b
Pa+Pb−Pa∗Pb ,这样我们只需要计算出每个节点的
P
a
和
P
b
P_a和P_b
Pa和Pb计算每个节点的
P
a
和
P
b
P_a和P_b
Pa和Pb：由于是随机选择的，所以每个节点被选择的概率是相等的，因此我们设每个节点都会选择一次，用path数组分别记录每个节点被两个人遍历的次数，最后将path除以N即算出每个节点分别被两个人遍历到的概率。path数组的求法（动态规划的思想）：从第N个节点向前遍历（不存在编号大的节点是编号小的节点的祖先），每个节点被遍历到的次数等于它前A步（或B步）的节点被遍历到的次数加1找到一个节点前A步（或B步）的节点：用par数组进行倍增查找（原理请查阅代码）
代码
#include<iostream>
#include<iomanip>
#include<vector>
#include<array>
using namespace std
;
int T
,A
[2],N
;
double re
;
int main(){
ios
::sync_with_stdio(0);
cin
.tie(0);
cin
>> T
;
for(int g
=1;g
<=T
;g
++){
re
=0;
cin
>> N
>> A
[0] >> A
[1];
vector
<array
<int,2>>path(N
+1);
vector
<int>deep(N
+1);
vector
<array
<int,20>>par(N
+1);
for(int i
=2;i
<=N
;i
++){
cin
>> par
[i
][0];
deep
[i
] = deep
[par
[i
][0]]+1;
for(int l
=0;par
[i
][l
];l
++){
par
[i
][l
+1] = par
[par
[i
][l
]][l
];
}
}
for(int i
=N
;i
>=1;i
--){
for(int j
=0;j
<=1;j
++){
path
[i
][j
] ++;
if(deep
[i
]<A
[j
])continue;
int v
= A
[j
],cur
=i
;
for(int l
=0;v
;v
>>=1,l
++){
if(v
&1)cur
= par
[cur
][l
];
}
path
[cur
][j
] += path
[i
][j
];
}
double pa
= (double)path
[i
][0]/N
;
double pb
= (double)path
[i
][1]/N
;
re
+= pa
+ pb
- pa
* pb
;
}
cout
<< "Case #" << g
<< ": " << fixed
<< setprecision(12) << re
<< "\n";
}
}
