Paint the Tree
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
You are given a rooted tree with N nodes. You would like to paint each node of the tree in one of three possible colors: red, green, and blue. The following conditions must be fulfilled:
- For each node painted red, there must be no more than R red nodes in its subtree (including this node).
- For each node painted green, there must be no more than G green nodes in its subtree (including this node).
- For each node painted blue, there must be no more than B blue nodes in it's subtree (including this node).
Find the number of ways to paint the tree and output it modulo 1000000007.
The first line contains four integers N, R, G and B.
The following N-1 lines contain pairs of the nodes' numbers Ui and Vi (one pair per line), describing the edges of the tree.
The nodes are numbered from 1 to N, inclusive, and the node with the index 1 is the root of the tree.
Output the answer to the problem on the first line.
- 1 ≤ N ≤ 300
- 0 ≤ R, G, B ≤ 300
Input #1: 3 1 1 1 1 2 3 1 Output #1: 12
Input #2: 8 2 1 3 1 2 1 4 5 4 7 4 3 2 4 6 8 6 Output #2: 613
|Tags||cook49, dynamic-programming, easy-medium, tree, witua|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.