思考题 with NFLS teachers

Husky

Miss Husky (Shiqi Hao) is the Art teacher of NFLS Class 8 Junior 3. She is a kind teacher.
But in fact, she is a spy working for NFLS. One day, she received the task to observe all the schools in Nanjing.
There are N schools numbered from 1 to N in Nanjing and some of them are connected by bidirectional roads. Each road has a length l_i and they form a shape of a tree. NFLS is the number 1.
Husky is going to choose a school she hasn't observed yet and move to that school by walking along the shortest path.
We define the tiredness of Husky as the sum of length of roads she walked along.
But things are getting harder. Each school has an anti-spy system. Formally, each school has an extra attribute safety point a_i(0\leq a_i \leq 1). If Husky is going to observe a school with safety point s, then there's a probability of s that Husky is found out spying. If Husky is found out spying, she will have to be sent back to the last school she observed by the headmaster of the school. Note that being sent back doesn't increase the tiredness of Husky.
What's more amazing is that Husky can turn into real Husky for at most K times. She can use this skill after having observed one school. Then she won't be found out nor feel tired at all. The skill's power goes out when she has observed another school.
What's the minimum expected value of tiredness of Husky? Note she don't need to return to NFLS.

Example

Input
tree={
[1,2,10],
[2,3,20]
}
safety={0,0.5,1}
K=1
Output
20
Explain
Husky can go from school 1 to 2 then to 3.
She can use the power when going from 2 to 3.
Then the total expected tiredness is \sum_{i=1}^{\infty}\frac{1}{2^i}\times10\times i=20

Constriant

Subtask 1(40%):N<=100000,K=0,Ai=0
Subtask 2(30%):N<=100000,K=0
Subtask 3(10%):N<=20
Subtask 4(10%):N<=1000
Subtask 5(10%):N<=100000