思考题 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

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

# 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