Would you please help me with a Nowcoder problem?

Revision en1, by Aveiro_quanyue, 2023-03-28 06:31:16

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 is reachable from u} |a_u - a_v|$$$

Tags tree, contribution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English Aveiro_quanyue 2023-03-28 07:06:04 63
en10 English Aveiro_quanyue 2023-03-28 06:56:17 0 (published)
en9 English Aveiro_quanyue 2023-03-28 06:56:12 14 (saved to drafts)
en8 English Aveiro_quanyue 2023-03-28 06:41:15 7 Tiny change: 'b.png)\n\nThe constraint: $2 \leq ' -> 'b.png)\n\nConstraints: $2 \leq '
en7 English Aveiro_quanyue 2023-03-28 06:39:25 0 (published)
en6 English Aveiro_quanyue 2023-03-28 06:39:08 62 (saved to drafts)
en5 English Aveiro_quanyue 2023-03-28 06:38:09 0 (published)
en4 English Aveiro_quanyue 2023-03-28 06:38:02 55
en3 English Aveiro_quanyue 2023-03-28 06:37:33 10
en2 English Aveiro_quanyue 2023-03-28 06:37:04 612
en1 English Aveiro_quanyue 2023-03-28 06:31:16 462 Initial revision (saved to drafts)