Mötesplats

문제

$NN$ stycken vänner bor på var sin nod i ett träd med $NN$ noder, där $NN$ är udda. Ett träd är en sammanhängande graf med exakt $N-1N-1$ kanter.

Vännerna vill nu alla träffas på en nod i trädet. De har kommit fram till att de vill mötas på den noden som minimerar summan av distanserna till vännerna, och har frågat dig om du kan hjälpa dem att hitta denna optimala mötesplats. Distansen $\text{dist}(a,b)\backslash text\{dist\}(a,b)$ mellan två noder $aa$ och $bb$ i trädet är antalet kanter på vägen mellan $aa$ och $bb$. Så formellt sett vill du hitta noden $xx$ som minimerar ${\sum }_{i=1}^n\text{dist}(x,i)\backslash sum\_\{i=1\}^\{n\}\; \backslash text\{dist\}(x,i)$.

Detta tänker du är ett lätt problem, och börjar genast koda en lösning. Men det finns en twist! Vännerna har dåligt minne och kommer inte ihåg hur trädet ser ut. Dock kommer de ihåg följande: givet tre olika vänner $a,b,ca,b,c$ kan de med säkerhet säga att de brukar mötas (när det bara är dem tre) på plats $xx$, där $xx$ är noden som minimerar $\text{dist}(x,a)+\text{dist}(x,b)+\text{dist}(x,c)\backslash text\{dist\}(x,a)\; +\backslash text\{dist\}(x,b)\; +\backslash text\{dist\}(x,c)$. Notera att $xx$ inte nödvändigtvis är en av noderna $a,ba,b$ eller $cc$.

I detta problem läser du alltså inte in grafen direkt i indatan, utan får istället fråga upp till $Q-1Q-1$ frågor på formen: Var brukar vännerna $a,b,ca,b,c$ mötas? Med hjälp av dessa frågor vill du hitta den optimala mötesplatsen.

[이미지 1]

Illustration av trädet i exempelfallet. Nod 2 är den optimala mötesplatsen.