I have run into a contest problem (ACM like) that sounds like this:
Input: a tree of $N$ nodes; integers $X,Y,Z$ such that $X+Y+Z=N$
Question: Can the tree be partitioned into three trees of $X,Y,Z$ nodes by removing only two edges?
I am promised that $N \le 10^5$. My code must finish within 200ms.
The brute-force method of generating all possible partitions of X, all possible partitions of Y, and all possible partitions of Z and checking if they form the tree is too slow. This got me thinking about dynamic programming. The only thing I see here to help me form a DP algorithm is counting how many children does a node have (treating the current node as a root of a tree). However, checking between the nodes themselves for X, Y, Z would still take $O(N^3)$ time, which is too much.
So do you see any other algorithm for this task?
Example: We're given a tree of 8 nodes and X = 3, Y = 3, Z = 2 and the following edges: 2-3; 4-2; 2-1; 1-5; 1-8; 5-6; 5-7. The answer is yes because you can delete edges 1-2 and 1-5 to form 3 partitions like this {1,8} (Z) and {2,3,4}/{5,6,7} (X/Y).
This problem is from a preparation stage of a local competition that happend a while back.