[learning notes] diameter and center of gravity of the tree

strawberry Strawberry

• Worship EternalAlexander
• hypothesis $|S|\ge 2$, Let the two ends of the diameter be $s$ and $t$
• Obviously we know that the diameter has a center
• If my starting point is not on the radius , Then I will occupy all the points in the radius next
• But obviously I can adjust the starting point to the radius , Then take all the points on the radius
• Then we find the maximum distance to the point on the radius for other points , After sorting, you can get $S\times G$ The maximum value of

CF1387B2

• For an edge $(u,v)$, Each side contributes up to $2\min (siz[u],n-siz[u])$
• Consider finding the center of gravity , Match the two span subtrees of points other than the center of gravity
• Because the size of any subtree does not exceed $\frac{n}{2}$, So there is a pairing scheme
• Let's not talk about the details

The diameter of the tree

• Given a tree , Seek number $[l,r]$ The maximum distance between two points in .$n\le 10^5$
• Consider two point sets on the tree $S$ and $T$, If we gather $S$ The farthest point in the pair is $u\to v$,$T$ The farthest point in the pair is $w\to x$, that $S\cup T$ The farthest point of must be $u\to v$,$w\to x$,$u\to w$,$u\to x$,$v\to w$,$v\to x$ One of six pairs
• You can maintain the line segment tree . We can use Euler sequence to find $LCA$ Balance the complexity to achieve preprocessing $O(n\log n)$, inquiry $O(1)$.
• The sum $O(n\log n)$.

Huffman tree (Hufman Tree)

• Construction method ： Take the two points with the smallest weight each time , Add a new node as their parent node , Set the new node weights to their prefixes and .