### Aveiro_quanyue's blog

By Aveiro_quanyue, history, 2 months ago,

Part 1: Problem Statement

A tree $T=(V, E)$ has $n$ vertices and $n-1$ edges, the weight of each vertex $i$ is $a_i$.

For each edge $e$, you can determine its direction, i.e., for two vertices $u, v$, there are two states: $u \rightarrow v$ and $v \rightarrow u$. There are $2^{n-1}$ states in total.

For each state $S$, we define $f(S)$ as

$f(S) := \sum\limits_{(u, v) \in V \times V, v\,\text{is reachable from}\,u} |a_u - a_v|$.

Compute the sum of $f(S)$ over all $2^{n-1}$ states $S$, modulo $998244353$.

Example:

Suppose $n=3$, and two edges connect $(1, 2), (2, 3)$, respectively. $a_1 = 3, a_2 = 1, a_3 = 2$, the answer is $14$.

Constraints: $2 \leq n \leq 2 \cdot 10^5$, $1 \leq a_i \leq 10^9$.

Part 2: My idea

My only attempt is using the counting twice trick:

$ans = 2\sum\limits_{(u, v) \in V \times V, u < v}|a_u - a_v|2^{n-1-d(u, v)} = \sum\limits_{(u, v) \in V \times V, u < v}|a_u - a_v|2^{n-d(u, v)}$, but I don't know how to solve it in $O(n)$ or $O(nlogn)$.

Maybe we could use $d(u, v) = d(u) + d(v) - 2d(lca(u, v))$?

• +12

»
2 months ago, # |
Rev. 10   -35

I think you can use Centroid Decomposition + Heuristic Merge to solve it.

Spoiler
•  » » 2 months ago, # ^ |   +6 I upvoted. Would you please elaborate on this please?
•  » » » 2 months ago, # ^ | ← Rev. 5 →   -23 Start with Centroid Decomposition (you can think of it as cdq on tree).Subsequently, at Centroid Decomposition, the points of the two subtrees are sorted by ai and multiplied by 2^(size of tree-dep of node) to make a prefix sum respectively, so that |ax-ay| becomes ∑ two ax-ay. I'm not sure how to analyze the complexity, maybe nlog^2n .
•  » » » » 2 months ago, # ^ |   +16 I think you are in the right direction. Please give me some times to figure out! Thanks for your idea.
•  » » » » » 2 months ago, # ^ |   -39 https://ac.nowcoder.com/discuss/1128009I found editorial, it is the same as my idea.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   +11 Thank you ShaoNian, I think you are super clever. I am not familiar with centroid decomposition at all, so it takes time for me to understand it. Hope you perform well in your coming CSP tests!PS. Are you the real ShaoNian?
• »
»
»
»
»
»
»
2 months ago, # ^ |
Rev. 5   -40

i'm Karry5307 and i'm good at ssh