USACO 170 DP tree-based Problem 'rivers' Analysis
by original analysis from IOI
It is not hard to observe that since for each village there is a unique way
down the river from the village to Bytetown, we can treat the rivers and
villages as a tree with the root in Bytetown. Nodes of the tree correspond to
the villages (for convenience we will refer to Bytetown as a village too), and
node v is the parent of node u when v is the first village downriver from u.
Let r denote the root of the tree, i.e. r corresponds to Bytetown. By depth(u)
we will denote the number of edges on a unique path from u to r. Clearly, the
values of depth(u) can be computed for all villages u in linear time. The
number of children of node u will be denoted by deg(u), and the number of trees
cut near village u will be denoted by trees(u).
We can apply dynamic programming to solve the task. Let Av,t,l denote the
minimal cost of transportation of the trees cut in the subtree rooted in v,
assuming that t additional sawmills can be built in the subtree, and the trees
not processed in v can be processed in the village of depth l (on the way from
v to Bytetown). We compute values of Av,t,l for each village v, and such
numbers t, l, that 0 <= t <= k and 0 <= l < depth(v). Clearly, when the tree
rooted in v has at most t nodes, then A(v,t,l) = 0, as we can simply place a
sawmill in every village. We can use the following formula:
A(v,t,l)=0 when the tree rooted in v has at most t nodes, min(A'v,t,l ,A''v,t )
otherwise.
where A'v,t,l is the cost of transportation when there is no sawmill in v, and
A''v0,t is the cost of transportation when there is one. These costs depend on
the distribution of sawmills between subtrees rooted in children of v. Let d =
deg(v) and let v1,v2, . . . ,vd be the children of v. Then:
A0v,t,l = trees(v) ·(depth(v)−l)+ min sum(i=1,d,Av_i,t_i,l)
t1+...+td=t
A0v0,t = min sum(i=1,d,Av_i,t_i,depth(v))
t1+...+td=t−1
The analysis then talked about DP one more time, however, this can be thought
as considering one more tree at a time and merging those results.