Hello everyone,
I'm struggling for a quite long time with certain problem (like 4 real attempts to solve it). Here is problem statement:
You are given a city which is represented by graph which is a tree (of course road intersections are nodes and roads are edges). Your task is to light every road in the city, you can do this by building street lights on road intersections. When there is street light on road intersection every road which comes out of it is lighted. Now your task is to find the minimum amount of street lights to light entire city and find amount of ways you can do this.
Input:
First line of input is n (n <= 100.000) — the number of road intersections in city. The next n-1 lines contain two integers a,b which mean that there is bidirectional road between intersections numbered a and b.
Output
First integer of output is optimal amount of street lights, and the second integer is the amount of optimal placements of streets lights in the city modulo 10007.
Examples:
Input:
4
1 2
2 3
3 4
Output: 2 3
Input:
5
1 2
2 3
3 4
4 5
Output:
2 1
Input:
6
1 2
2 3
1 4
4 5
1 6
Output:
3 5
Finding optimal number of street lights is quite simple, just two-color the tree and take the less often color. However finding amount of optimal street light placements is really hard for me. I was trying to root the tree at some node, and then find recurrence relation between node and its children so i can use dynamic programming. I believe in order to solve this problem one has to use at least two functions, h(v) — which is answer to the problem when there is street light in node v (where v is root of subtree), and l(v) when there is no street light at node (v), i tried to use some other functions like opt(v) — which represents optimal amount of street lights at subtree rooted at node v, but i just couldn't come up with recurrence relation.
Does anyone have any idea on how to solve this problem ?
Full text and comments »