ZigZag Tree Sequences (Hard)

**This is the hard version of the problem. In this version, the labels of the nodes $A_i$ satisfy $A_i \le N$. This problem is worth $65$ points in division $1$, and is not scorable in the other divisions.** You are given a labeled tree on $N$ nodes. Node $i$ has the label $A_i$. Count the number of zig-zag sequences in it. Formally, a sequence of nodes $v_1, v_2, v_3, \ldots, v_k$ of lengt