For a fixed root, there are two kinds of path: the ones which pass the root and the ones which don't. The first kind is special since we can seperate a path $(a,b)$ into $(a,r)$ and $(r,b)$, which might be easier to deal with via proper preprocessing. Consider following divide and conquer procedure:
Solve(T):
Fix a root r
for each a
for each b s.t. (a,b) pass r
AR[a]+=calc(a,b)
for each branch T_i of r (which is also a tree)
Solve(T_i)
Note that we neither miss a pair nor count a pair twice since $(a,b)$ don't pass $r$ if and only if they are in the same branch. In addition, it's not hard to prove that trees in depth-$d$ recursive call don't overlap. Therefore, if we can do the non-recursive part in $O(\text{size of tree})$, the complexity would be $O(\text{recursive depth}\times n)$. If we always choose $r$ as the centroid, recursive depth is bounded by $O(\log n)$ and hence the complexity would be $O(n \log n)$. Now let's see how to solve the non-recursive part.
For a pair of node $(a,b)$, let $\text{path}(a,b)$ denote the set of distinct values on the path from $a$ to $b$, and $I_{ab}(v)$ denote the indicator function which is $1$ when $v\in \text{path}(a,b)$ and $0$ otherwise. It's not hard to see $\text{calc}(a,b)=|\text{path}(a,b)|=\sum_vI_v$.
Recall that in each phase, we choose the centroid $r$ as the root and consider only the paths passing the root. Let $B_a={b\in T:(a,b)\text{ pass }r}$. Using the indicator function above, we have $\sum_{b\in B_a}\text{calc}(a,b)=\sum_{b\in B_a}\sum_v I_{ab}(v)=\sum_v\sum_{b\in B_a} I_{ab}(v)$. 743
Therefore, computing $\sum_{b\in B_a} I_{ab}(v)$ for each $a$ and $v$ also gives us the answer. (You can interpret this as the number of $b$ such that $v\in \text{path}(a,b)$.) To do this, consider the set $S$ for each value $v$ such that $S_T(v)={u\in T: v\in\text{path}(r,u)}$. We need to maintain $|S(v)|$ for the whole tree and similarly $|S_i(v)|$ for the $i$-th branch of $r$. We will see how to implement this later.
Since $B_r=T$, $\sum_{b\in B_r}\text{calc}(r,b)$ is exactly $\sum_v|S(v)|$. Next, consider node $a$ in the $i$-th branch. Let $r_i$ denote the $i$-th child of $r$. For each node $b$ which is not in the $i$-th branch, we can split path $(a,b)$ into $(r,b)$ and $(r_i,a)$. Therefore, $$\sum_{b\in B_a}\text{calc}(a,b)=\sum_{b\in B_a}\text{calc}(r,b)+\sum_{b\in B_a}|\text{path}(r_i,a)\backslash\text{path}(r,b)|$$ It's not hard to see that the first term equals to $\sum_v(|S_T(v)|-|S_i(v)|)$, so let's focus on the second term. Now consider each node $u$ on the path from $r_i$ to $a$ and count $\text{value}[u]$ one by one. There are two possible cases:
1. $\text{value}[u]=\text{value}[u']$ for some $u'\neq u$ on the path from $r_i$ to $u$. 743