Блог пользователя Aveiro_quanyue

Автор Aveiro_quanyue, история, 12 месяцев назад, По-английски

Part 1: Problem Statement

Link

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
  • Проголосовать: не нравится

»
12 месяцев назад, # |
Rev. 10   Проголосовать: нравится -35 Проголосовать: не нравится

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


Spoiler
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    I upvoted. Would you please elaborate on this please?

    • »
      »
      »
      12 месяцев назад, # ^ |
      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 .