MathDB
Longest paths in a tree

Source: Iran 3rd round 2012-Combinatorics exam-P3

September 20, 2012
combinatorics proposedcombinatorics

Problem Statement

In a tree with nn vertices, for each vertex xix_i, denote the longest paths passing through it by li1,li2,...,likil_i^1,l_i^2,...,l_i^{k_i}. xix_i cuts those longest paths into two parts with (ai1,bi1),(ai2,bi2),...,(aiki,biki)(a_i^1,b_i^1),(a_i^2,b_i^2),...,(a_i^{k_i},b_i^{k_i}) vertices respectively. If max⁡j=1,...,ki{aij×bij}=pi\max_{j=1,...,k_i} \{a_i^j\times b_i^j\}=p_i, find the maximum and minimum values of ∑i=1npi\sum_{i=1}^{n} p_i.
Proposed by Sina Rezaei
Back to ProblemsView on AoPS