e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

Містер В

Друзі подарували Містеру В $n$ бусин пронумерованих цілими числами від $1$ до $n$. Герой з'єднав буси $(n-1)$-ою ниткою так, щоб утворилось намисто. Оскільки Містер В, програміст то намисто має деревоподібну структуру. Будував намисто Містер В наступним чином: спочатку він вибрав деяку початкову бусину, після чого $(n-1)$ раз додавав одну бусину до свого намиста. Бусину він міг додати одним з наступних способів: герой або вибирав деяку бусину, що вже належить намисту та з'єднував її з бусиною, що ще не належить намисту червоною ниткою, або ж він вибирав деяку пару бусин з намиста що з'єднані червоною ниткою після чого роз'єднував їх та з'єднував синьою ниткою кожну з них з бусиною, яку зараз додає до намиста. Нитки, що з'єднують буси намиста, можуть мати різні довжини. Містер В записав структуру намиста, після чого подарував його Місіс В. Але от халепа~--- герой забув кольори ниток в намисті. Допоможіть йому дізнатись максимально можливу суму довжин синіх ниток намиста, адже саме це значення його дуже зацікавило. \InputFile Перший рядок містить одне ціле число $n$ ($1\le n\le 2\cdot 10^5$)~--- кількість бусин намиста. Кожен з наступних $n-1$ рядків містить по три цілі числа $u$,$v$ та $l$ ($1\le u<v\le n$, $1\le l\le 10\,000$)~--- номери бусин, які з'єднує відповідна нитка, та її довжина. \OutputFile Виведіть одне ціле число~--- максимально можливу суму довжин синіх ниток намиста. \Note У першому прикладі Містер В міг почати будувати намисто з бусини з номером $3$, після чого з'єднати бусину з номером $3$ з бусиною з номером $5$ червоною ниткою, потім роз'єднати бусини з номерами $3$ і $5$ та з'єднати бусини з номерами $1$ і $3$ та $1$ і $5$ синіми нитками, потім з'єднати бусини з номерами $1$ і $2$ червоною ниткою і останнім кроком з'єднати бусини з номерами $1$ і $4$ червоною ниткою. Таким чином сума довжин синіх ниток буде рівною $60$. \Scoring \begin{enumerate} \item ($13$ балів): $1\le n\le 10$; \item ($15$ балів): $1\le n\le 200$; \item ($29$ балів): $1\le n\le 10000$; \item ($43$ бали): без додаткових обмежень. \end{enumerate}
Time limit 1 second
Memory limit 256 MiB
Input example #1
5
1 2 10
1 3 40
1 4 15
1 5 20
Output example #1
60
Input example #2
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
Output example #2
140
Author Ihor Barenblat