Problem 3: Grass Planting [Travis Hance, 2011]

Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional roads, such that there is exactly one path between any two pastures.

Bessie, a cow who loves her grazing time, often complains about how there is no grass on the roads between pastures.

Farmer John loves Bessie very much, and today he is finally going to plant grass on the roads.

He will do so using a procedure consisting of M steps (1 <= M <= 100,000).

At each step one of two things will happen: - FJ will choose two pastures, and plant a patch of grass along each road in between the two pastures, or, - Bessie will ask about how many patches of grass on a particular road, and Farmer John must answer her question.

Farmer John is a very poor counter -- help him answer Bessie's questions!

#3746 upload -회 done -회 how_to_reg -명 stop_circle 채점 보류

USACO 2011 December Contest, Gold Division - Grass Planting timer 1초 memory 128MB

#3746
채점 보류

USACO 2011 December Contest, Gold Division - Grass Planting 1초 128MB