Dynamic Beautiful Tree Lamp Count

Given a rooted tree with \(n\) nodes (node \(1\) is the root) and \(n-1\) lamps assigned to each non-root node. You are given a permutation \(a_1,a_2,\dots,a_{n-1}\) of \(\{2,3,\dots,n\}\). Initially, all lamps are off and a counter is set to \(0\).

The process is as follows: Lamps are turned on one by one in the order of the permutation. After each lamp activation, if the tree is beautiful, the counter is increased by the number of connected components formed by the lit nodes. A tree is defined to be beautiful if for every lit node \(v\), all nodes in the subtree of \(v\) (with respect to the tree rooted at \(1\)) are lit. In other words, if \(T(v)\) represents the subtree of \(v\), then for every \(v\) with its lamp on, we must have \[ \forall u \in T(v), \quad \text{lamp}(u) \text{ is on}. \]

After all \(n-1\) lamp operations, the final value of the counter is the answer for that tree.

After the initial configuration, there are \(q\) modifications. Each modification consists of removing an edge and then adding a new edge such that the resulting graph remains a tree. For each modification, the counter is reset to \(0\), and the whole lamp turning on process (following the same permutation) is repeated on the new tree. Your task is to compute and output the answer for each modification.

All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(q\) (with \(n\ge2\) and \(q\ge1\)). The second line contains \(n-1\) integers \(a_1,a_2,\dots,a_{n-1}\) which form a permutation of \(\{2,3,\dots,n\}\).

The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge of the tree.

Then \(q\) lines follow. Each query consists of four integers \(u\), \(v\), \(x\), and \(y\) indicating that the edge \((u,v)\) is removed and the edge \((x,y)\) is added. It is guaranteed that after each modification the graph remains a tree.

outputFormat

For each modification, output a single integer on a new line --- the computed answer of the tree after performing the lamp activation process.

sample

3 1
2 3
1 2
1 3
1 2 2 3

2