Try printing out the pv values in your dfs2 method on this case: 12 1 3 3 1 1 1 1 1 1 1 3 1 1 2 2 10 1 3 3 4 7 9 3 5 5 7 7 8 1 11 11 12 3 6

You should see that many of these values are greater than 11 (which shouldn't be possible because given some fixed vertex, there are at most 11 other nodes a path can end at).

While your code technically gives the correct answer on this case (as it's trivially 0), for your type 2 paths, you only want to consider the number of paths starting from c which end at a node that's not in c's subtree and have exactly 2 nodes with the same value along the path (similar to the condition in type 1). Not accounting for this results in massive over-counting which accumulates in the pv values.

I'm not sure how you'd actually efficiently compute this in one dfs.

This fails on 4 1 2 1 1 1 2 2 3 3 4 (Test 104)

It's because the '1,1' path in the subtree of 2 isn't accounted for by your two possible types.