Tree Operations (Hard)

**This is the hard version of the problem. The only difference is that here, $1 \le Q \le 2 \cdot 10^5$. This version is worth $100$ points in Division $1$ and unscoreable in other divisions.** You are given a tree with $N$ nodes, rooted at $1$. Each node $i$ has an associated non-negative integer value $A_i$. The **score of a tree** is defined as the minimum number of times you need to apply th