Conjunto Independente Máximo em Árvore

#182

Made by: Crazynds

100MB

0.1s

Dada uma árvore com $N$ nós, onde cada nó $i$ possui um peso $w_i$, selecione um subconjunto independente de nós — nenhum par de nós selecionados pode ser adjacente na árvore — de forma a maximizar a soma dos pesos.

Input

A primeira linha contém um inteiro $N$ $(1 \le N \le 10^5)$.

A segunda linha contém $N$ inteiros $w_i$ $(1 \le w_i \le 10^9)$, os pesos de cada nó.

As próximas $N-1$ linhas contêm dois inteiros $u$ e $v$, representando uma aresta entre os nós $u$ e $v$.

Output

Imprima um único inteiro: a soma máxima de um conjunto independente.

Input Example

Output Example

7
10 5 3 4 6 2 8
1 2
1 3
2 4
2 5
3 6
3 7

Explanation 1:
A árvore tem raiz 1. Uma seleção ótima é os nós $\{1, 4, 5, 6, 7\}$ com pesos $10+4+6+2+8 = 30$

1
42

27
708504 906506 39265 914954 573010 90935 430707 831539 505999 945429 67031 987863 474663 836337 484832 821976 22130 106923 33573 365619 904394 365607 497259 476417 861126 35529 674730
1 2
2 3
1 4
4 5
2 6
5 7
4 8
6 9
7 10
9 11
3 12
10 13
13 14
3 15
7 16
1 17
12 18
14 19
19 20
17 21
19 22
13 23
16 24
1 25
25 26
2 27