Maksimal məbləğ ağacda

Ağac $n$ zirvədən ibarətdir, burada $i$ nömrəli zirvə $(1\le i\le n)$ $c_i$ sikkəyə malikdir. Siz elə bir zirvələr altmüxtəlifliyi seçməlisiniz ki, onların heç biri qonşu olmasın (yəni zirvələr bir kənarla birləşməsin) və seçilmiş zirvələrdəki sikkələrin cəmi maksimum olsun.

Giriş verilənləri

Birinci sətir ağacdakı zirvələrin sayını $n(1\le n\le 10^5)$ ehtiva edir. Növbəti $n-1$ sətirin hər biri ağacdakı bir kənarı təyin edən iki ədəd $u$ və $v(1\le u,v\le n)$ ehtiva edir. Sonuncu sətir ağacın zirvələrindəki sikkələrin sayını göstərən $n$ tam qeyri-mənfi ədəd $c_1,...c_n$ ehtiva edir.

Çıxış verilənləri

Seçilmiş zirvələr altmüxtəlifliyindəki sikkələrin mümkün olan ən böyük cəmini çıxarın.

Nümunələr