| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
BIRTHDAYTREE - Ծննդյան ծառը |
Հունվարի 29-ին Հայկի ծննդյան օրն էր, և նրա մեծ եղբայրը ծննդյան առթիվ Հայկին նվիրել էր n գագաթ պարունակող գրաֆ, որն իրենից ներկայացնում էր ծառ (ծառը դա n-1 կող պարունակող կապակցված գրաֆն է)։ Քանի որ Հայկը շատ է սիրում լուծել տարբեր խնդիրներ, նա խնդրում է մեծ եղբորը տալ նրան ինչ-որ խնդիր, որը կապված կլինի իր նվերի հետ։ Հայկին տրվում է հետևյալ խնդիրը. Տրված է n գագաթ պարունակող ծառ, որի կողերը ունեն երկարություններ։ Յուրաքանչյուր գագաթի համար անհրաժեշտ է գտնել այդ գագաթից դեպի մյուս գագաթներ հեռավորությունների գումարը։
Մուտքային տվյալներ
Մուտքային տվյալների առաջին տողում տրված է մեկ ամբողջ թիվ՝ ծառի գագաթների n (2 ≤ n ≤ 105) քանակը։ Հաջորդ n-1 տողերից յուրաքանչյուրում տրված են երեք ամբողջ u, v, w (1 ≤ u ≠ v ≤ n, 1 ≤ w ≤ 105), որը նշանակում է, որ v գագաթը u-ին միացված է w երկարությամբ կողով։
Ելքային տվյալներ
Արտածեք n ամբողջ թիվ, որոնցից i-րդը՝ i գագաթի յուրահատուկ գումարն է։
Օրինակ
| Մուտք | Ելք |
|---|---|
| 5 1 2 3 2 3 4 3 4 5 4 5 2 |
36 27 23 28 34 |
| 6 1 2 3 1 3 4 1 6 7 3 4 1 3 5 2 |
25 37 25 29 33 53 |
Բացատրություն
Առաջին օրինակում, 3-րդ գագաթի անհրաժեշտ գումարը հաշվվում է հետևյալ կերպ.
- 3 համարի գագաթից դեպի 1 համարի գագաթ հեռավորությունը հավասար է 7-ի։
- 3 համարի գագաթից դեպի 2 համարի գագաթ հեռավորությունը հավասար է 4-ի։
- 3 համարի գագաթից դեպի 4 համարի գագաթ հեռավորությունը հավասար է 5-ի։
- 3 համարի գագաթից դեպի 5 համարի գագաթ հեռավորությունը հավասար է 7-ի։
Հետևաբար 3-րդ գագաթի համար պատասխանը հավասար է 7+4+5+7=23:
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2022-02-06 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Մարզային փուլ, 2021-22 |
RSS