# Lönnträd

## N² / 2 + O(N log N)

- Fixera en godtycklig nod som rot för trädet.
- Med hjälp av oraklet, sortera alla noder utifrån ökande avstånd från roten.
(Implementationsdetalj: i C++ går det att använda `std::sort(..., [&](int a, int b) { return (är a mindre än b?); })` för att sortera utifrån en komparator; i Python får man definiera en egen klass med en `__lt__`-metod eller använda `functools.cmp_to_key`. Det går också att skriva sin egen sorteringsalgoritm förstås, det är bra övning.)
- Gå igenom noderna från sista till första. För varje nod kan vi hitta dess förälder bland noderna innan den i listan genom att gå igenom dem alla och hitta den som är närmast.
- Antalet queries är $O(N \log N)$ för sortering, plus $N+(N-1)+(N-2)+\ldots+1 \approx N^2/2$ för föräldrasökande. Det här löser de första två delpoängen.

## Linjefallet, i O(N log N)

- Välj en godtycklig nod.
- Hitta noden som är längst bort från den: den måste vara en av linjens ändnoder.
- Som i lösningen ovan, sortera noderna utifrån avstånd till den hittade noden. Linjegrafen kommer nu bestå av noderna i den ordningen.

## Linjefallet, finare lösning

- Välj en slumpmässig nod, säg $x$.
- Hitta noden som är närmast den, säg $y$. Kanten $(x, y)$ måste vara del av trädet.
- Gå igenom alla noder, och placera varje nod i mängd "vänster" eller "höger" beroende på om den är närmast $x$ eller $y$.
- Rekursera på vänster och höger mängd.
- Varje splittning kommer dela mängden i två hyfsat stora delar, inte riktigt 50/50 men inte heller så långt ifrån i genomsnitt. Tidskomplexiteten ges av $T(n) \approx n + 2 T(n/2)$ vilket blir $T(n) = O(n \log n)$, i likhet med quick sort. (Det går förstås att göra den här analysen mindre slarvig.) Det är möjligt att konstantfaktorn är för dålig för att klara linjetestgruppen; vi har inte faktiskt testat.

## Det allmänna fallet i O(N log N)

Det är lockande att försöka lösa det allmänna fallet på samma som den finare lösningen för linjefallet ovan. Men det fungerar inte riktigt: en slumpmässigt vald kant behöver inte i genomsnitt dela upp trädet speciellt väl, t.ex. i fallet med ett välbalanserat binärt träd. I stället måste vi först hitta en någorlunda central nod i trädet som vi kan dela upp kring. [Centroiden](https://www.geeksforgeeks.org/centroid-decomposition-of-tree/) vore bra, till exempel.

Givet tre noder går det att hitta medianen av de tre noderna (d.v.s. noden som minimerar summan av avstånd till alla tre) genom att börja med godtycklig nod vald, och sen gå igenom alla noder och upprepat fråga sig huruvida den nya noden skulle förbättra avståndet till minst två av noderna relativt vår nuvarande mediankandidat. (Det här blir tydligare om man ritar en bild.)

Vi kan nu tänka oss följande algoritm:
- Välj tre slumpmässiga noder. Hitta deras median, $x$.
- Hitta noden som är närmast $x$; kalla den $y$. Dela in noder i vänster/höger baserat på $x$/$y$, och rekursera på båda delar.

En kant som angränsar till en slumpmässig median är tillräckligt nära mitten för att det här ska vara $O(N \log N)$ i genomsnitt, med en konstantfaktor som är tillräcklig för att lösa testgrupp 3.

Notera att det enbart är för att varje nod gränsar till högst 3 andra som uppdelningen kring kant $(x, y)$ är effektiv: om t.ex. stjärngrafer hade varit tillåtna hade det inte stämt, och problemet hade i själva verket varit omöjligt att lösa i $O(N \log N)$.

## Det allmänna fallet i O(N log N), alternativ lösning

Som ett mindre probabilistiskt alternativ till ovanstående lösning kan vi tänka oss följande:
- Välj en rotnod på måfå.
- Sortera resten av noderna med avseende på ökande avstånd från rotnoden, med hjälp av oraklet.
- Gå igenom noderna *från första till sista* (i motsats mot vad vi gjorde tidigare). För varje nod vill vi hitta dess förälder i det träd vi hittills konstruerat, vilket kommer att vara den nod som är närmast i trädet.
- För att hitta föräldern "binärsöker" vi i vårt träd. Vi hittar upprepat en kant $(x, y)$ som skär trädet i så nära 50/50 som möjligt, och kollar om det är $x$ eller $y$ som är närmast den nya noden. Beroende på svaret kan vi på ett ungefär halvera storleken på träddelgrafen där den närmaste noden finns.
- Ett logaritmiskt antalet binärsökningsiterationer per nod ger oss en tidsåtgång på ytterligare $O(N \log N)$ ovanpå sorteringen, och så även totalt $O(N \log N)$.

För att få optimal konstantfaktor krävs att sorteringssteget använder sig av rätt sorteringsalgoritm. T.ex. kommer `std::sort` i C++ typiskt inte att fungera: GCC implementerar `std::sort` med hjälp av quick sort, som är probabilistisk och kan ha otur och kräva ett onödigt stort antal jämförelser. Ett välfungerande alternativ är merge sort, som använder sig av ganska exakt $N \log_2 N$ jämförelseoperationer och i C++ går att använda medelst `std::stable_sort`.

Denna lösning använder sig av ungefär 18400 queries som mest över alla testfall, och får full poäng.

# Den generösa resenären
## Subtask 2
Notice that we have a line graph, which is essentially an array. To quickly answer queries using $A_i \leq 100$, we want to be able to quickly jump to the next city where we give away money. We will do this at most $100$ times, so in total, we get $O(100(N+Q))$.
To be able to jump quickly, precompute the following: for each position $i \in[0,N-1)$ and value $v \in [1,100]$, compute the first element to the left and right that is $\geq v$. This can be done by keeping sweeping left to right (and vice versa), keeping a stack of indices waiting to be assigned an element to the right that is larger.

## Subtask 3
To solve this subtask, we need the most important observation for this whole task: when we modulo a number, it either remains unchanged or is decreased to at least half of its value before being modulo'd. Suppose we have the number $x$ and we modulo it by $A$, there three cases:
- If $A > x$, $x$ is unaffected
- If $A \leq \frac{x}{2}$, then it can be seen that after the modulo, $x$ must be strictly less than $A$.
- If $\frac{x}{2} < A \leq x$, then $x$ mod $A$ = $x-A$, which reduces to the second case.

(Proof taken from [Usaco Guide](https://usaco.guide/adv/segtree-beats?lang=cpp#solution---the-child-and-sequence)).

Thus, if we can quickly find the next element $\geq x$ in $O(T)$ time, then we can answer every query in $O(T \log(x))$. This is because we can only divide $x$ by 2 log times before it reaches 0.

Note that the precomputation from before won't work as $x$ is large. There are two common ways to solve this subproblem.
- Binary search for the smallest $j > i$ where the smallest number in $[i,j]$ is $\geq x$. This either gives $O(\log(N)^2)$ using segment trees for the RMQ (range min query), or $O(\log(N))$ using sparse tables.
- Do a [walk on the segment tree](https://usaco.guide/plat/segtree-ext?lang=cpp#walking-on-a-segment-tree).

Due to the high time limit, $O(\log(N)^2 \log(x))$ per query probably passes.

## Subtask 4
We need to generalize the previous solution to trees. In this subtask, if we root the tree at node $1$, then all queries only go up towards the tree. It seems that the approach where we binary search for the ancestor closest to us that has $A$ value $\geq x$. This can be done in $O(\log(N))$ time using binary lifting.

## Subtask 5
Whenever we have a path $a \rightarrow b$ in a tree, it is common to split it into two paths $a \rightarrow lca(a,b)$ and $b \rightarrow lca(a,b)$, since it's easier to go up rather than down in a tree. However, in this problem, order matters; we can't go $b \rightarrow lca(a,b)$, we *must* go $lca(a,b) \rightarrow b$. For the path $lca(a,b) \rightarrow b$, we can still binary search for how down we should go from the lca. The annoying part is that this gives us path min queries that are hard to answer in less than $O(\log(N))$ time. In total, we get $O(\log(N)^2 \log(x))$, which is likely fast enough due to the high time limit.

There are two ways to instead achieve $O(\log(x) \log(N))$ time per query. One is by speeding up path min queries to $O(1)$ using the [kruskal reconstruction tree](https://mzhang2021.github.io/cp-blog/kruskal/).
The other, less exotic alternative is by using heavy-light decomposition. For every path in the HLD, create a sparse table. This gives $O(\log(N)+\log(N) \log(x))$ time per query. This was the intended solution.