HBC24727msc的背包,生成函数,数学[USACO 2010 Feb G]Slowing down题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

Every day each of Farmer John's N (1

Every day each of Farmer John's N (1 <= N <= 100,000) cows conveniently numbered 1..N move from the barn to her private pasture. The pastures are organized as a tree, with the barn being on pasture 1. Exactly N-1 cow unidirectional paths connect the pastures; directly connected pastures have exactly one path. Path i connects pastures A_i A i ​ and B_i B i ​ (1 <= A_i A i ​ <= N; 1 <= B_i B i ​ <= N). Cow i has a private pasture P_i P i ​ (1 <= P_i P i ​ <= N). The barn's small door lets only one cow exit at a time; and the patient cows wait until their predecessor arrives at her private pasture. First cow 1 exits and moves to pasture P_1 P 1 ​ . Then cow 2 exits and goes to pasture P_2 P 2 ​ , and so on. While cow i walks to P_i P i ​ she might or might not pass through a pasture that already contains an eating cow. When a cow is present in a pasture, cow i walks slower than usual to prevent annoying her friend. Consider the following pasture network, where the number between parentheses indicates the pastures' owner. 1 (3) / (1) 4 3 (5) / (2) 2 5 (4) First, cow 1 walks to her pasture: 1 (3) / [1] 4* 3 (5) / (2) 2 5 (4) When cow 2 moves to her pasture, she first passes into the barn's pasture, pasture 1. Then she sneaks around cow 1 in pasture 4 before arriving at her own pasture. 1 (3) / [1] 4* 3 (5) / [2] 2* 5 (4) Cow 3 doesn't get far at all -- she lounges in the barn's pasture, #1. 1* [3] / [1] 4* 3 (5) / [2] 2* 5 (4) Cow 4 must slow for pasture 1 and 4 on her way to pasture 5: 1* [3] / [1] 4* 3 (5) / [2] 2* 5* [4] Cow 5 slows for cow 3 in pasture 1 and then enters her own private pasture: 1* [3] / [1] 4* 3*[5] / [2] 2* 5* [4] FJ would like to know how many times each cow has to slow down.

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC24727msc的背包 生成函数 数学[USACO 2010 Feb G]Slowing down题解