Tree Requirements (Hard)

**This is the hard version of the problem. The only difference between this and easy version is the constraints on $N$ and $M$ — notably, in this version, $N, M \leq 2\cdot 10^5$.** You are given a tree with $N$ nodes. Each node $i$ has an associated value $A_i$. You can choose some subset $S$ of the $N$ nodes. You are given $M$ requirements that $S$ should satisfy, each of the form: - $(u, r, k