思考题 for blue boy

Roguelike Tree

Statement

You are given a tree of N nodes. Each node could be 3 status: passable(.), impassable(X), unknown(?).
Now we randomly replace each "unknown" to "passable" or "impassable" then we need to find out the expected value of connected node pairs.
We call two nodes connected, if the path between them won't pass any impassable nodes.

Examples

5
. X ? ? .
1 2
2 3
1 4
4 5

Output:

1.5

Explain:

If 3='.' 4='.' then pairs={1,4} {4,5} {1,5}
If 3='.' 4='X' then pairs=none
if 3='X' 4='.' then pairs={1,4} {4,5} {1,5}
if 3='X' 4='X' then pairs=none

Constriants

Subtask 1(10%) 1<=n<=10
Subtask 2(10%) 1<=n<=1000, no '?'
Subtask 3(10%) 1<=n<=10^5, no '?'
Subtask 4(20%) 1<=n<=1000
Subtask 5(15%) 1<=n<=10^5, only count pairs with 1.(i.e. pair {x,y} only counts when x=1 or y=1)
Subtask 5(35%) 1<=n<=10^5
**Orange boy comes and ac*