This problem looks like a fairly standard tree DP problem, I won't spoil the solution in case people want to think about it.
However, the reason why this problem is interesting (or perhaps extremely painful) is that the memory limit is 32MB. Given that $$$N$$$ can be 1.5 million, this means you're not even allowed to store $$$6N$$$ 32-bit integers.
Therefore, it seems that the main challenge of this problem is to be able to fit everything inside such a tight memory limit. Notably, I've gotten MLE just trying to read in the input and trying to get the tree stored in a representation that makes it possible for me to start working on the DP part of the problem.
In the modern era, memory limits are no longer this tight, but a lot of problems on szkopul retain these tight memory limits which occasionally makes it an interesting (or perhaps extremely painful) challenge to figure out how to fit things in the memory limit.
What's intended here? I asked about this problem in the AC server and got some advice with things such as relabeling the tree with ETT or simulating DFS without an explicit stack. It feels like the authors intended for some precise $$$5N + \mathcal{O}(1)$$$ memory solution and it's a little alarming that I can't even get beyond "read the input and come up with some representation for the tree" without getting MLE.
Solution to matching.
That was quite cool. I know many would hate it, but I wouldn't mind more problems with this level of thinking needed to be put in memory management.
Just FYI, that was the intention. :]
The author of the problem here. TL;DR: Yes, small memory limit was intended. In fact you can solve it with even smaller memory.
I agree that memory limits for some old Szkopul problems are quite tight by today's standards, and probably should be increased. (Back in the old days we often had 8 MB limit for the stack, so sometimes even writing simple DFS on a tree was painful.) But in this problem dealing with memory is the main challenge.
As an author, every now and then I like to propose a problem of experimental or technical nature, or challenging implementation-wise. I know that some people dislike such problems, but I enjoy them. The idea for the "Matchings" problem came to me when I noticed that memory limits for tree problems tend to be quite big when compared to other problems (even graph ones). It is due to the fact that both vector representation for very sparse graphs, and recursion needed for DFS are memory-demanding. So I asked myself: what is the minimal amount of memory you need to solve a non-trivial DP problem on a tree?
When I proposed this problem in 2010, the intended memory consumption was in fact $$$5N + O(1)$$$ ints. It required replacing vectors and recursion with hand-crafted code, and also some memory reusage. I was quite happy with the model solution, but I didn't know whether it was optimal or not.
Then I reused this problem in 2015 at the other camp, and once more gave it some serious thinking, and after figuring out some additional tricks for heavy memory reusage I was able to squeeze it in only
$$$2N + O(1)$$$ ints.
For me it was very surprising that you could achieve this, and I documented my story with this problem for posterity.
So you can see that 32 MB is quite a loose memory limit, after all. :D
This problem ended up being a lot of fun. Thanks for sharing!