Ancestor Difference on a Tree (Maximum)

# Maximum Ancestor Difference on a Tree ## Problem Statement You are given an undirected tree with $n$ nodes, rooted at node $1$. Each node $i$ has an integer weight $w_i$. For every node $i$, you need to compute $M_i$, defined as the maximum absolute difference between $w_i$ and the weight of any of its ancestors. Formally, $$M_i = \max_{u \in \text{Ancestors}(i)} |w_i - w_u|$$ where $\text{Ancestors}(i)$ denotes the set of nodes on the unique path from the root (node $1$) to the parent of node $i$. For the root node $1$, since it has no ancestors, $M_1$ is defined as $0$. ## Input Format - The first line contains a single integer $n$ ($1 \le n \le 10^5$), representing the number of nodes in the tree. - The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($-10^9 \le w_i \le 10^9$), where $w_i$ is the weight of node $i$. - Each of the next $n-1$ lines contains two integers $u, v$ ($1 \le u, v \le n$, $u \neq v$), denoting an edge between node $u$ and node $v$. These edges form a valid tree, and it is rooted at node $1$. ## Output Format Print $n$ integers $M_1, M_2, \dots, M_n$, separated by spaces, where $M_i$ is the required maximum absolute difference for node $i$. ## Sample Test Cases ### Sample Input 1 ``` 5 5 1 7 6 2 1 2 1 3 2 4 2 5 ``` ### Sample Output 1 ``` 0 4 2 5 3 ``` ### Sample Input 2 ``` 4 10 10 10 10 1 2 2 3 3 4 ``` ### Sample Output 2 ``` 0 0 0 0 ``` ## Constraints - $1 \le n \le 10^5$ - $-10^9 \le w_i \le 10^9$ - $1 \le u, v \le n$, $u \neq v$ - The given edges always form a tree. - The tree is rooted at node $1$. - Time limit: 1 second - Memory limit: 256 MB ## Explanation For Sample 1: - For node $1$ (root), $M_1 = 0$. - For node $2$ ($w_2=1$), its only ancestor is node $1$ ($w_1=5$). So, $M_2 = |w_2 - w_1| = |1 - 5| = 4$. - For node $3$ ($w_3=7$), its only ancestor is node $1$ ($w_1=5$). So, $M_3 = |w_3 - w_1| = |7 - 5| = 2$. - For node $4$ ($w_4=6$), its ancestors are node $1$ ($w_1=5$) and node $2$ ($w_2=1$). So, $M_4 = \max(|w_4 - w_1|, |w_4 - w_2|) = \max(|6 - 5|, |6 - 1|) = \max(1, 5) = 5$. - For node $5$ ($w_5=2$), its ancestors are node $1$ ($w_1=5$) and node $2$ ($w_2=1$). So, $M_5 = \max(|w_5 - w_1|, |w_5 - w_2|) = \max(|2 - 5|, |2 - 1|) = \max(3, 1) = 3$. For Sample 2, all weights are identical. Thus, the absolute difference with any ancestor will always be $0$, resulting in $M_i = 0$ for all $i$.