Nested Rubber Bands (Codeforces 1338D)
Tags: Math, trees

You have a tree of $$$n$$$ vertices. You are going to convert this tree into $$$n$$$ rubber bands on infinitely large plane. Conversion rule follows:  For every pair of vertices $$$a$$$ and $$$b$$$, rubber bands $$$a$$$ and $$$b$$$ should intersect if and only if there is an edge exists between $$$a$$$ and $$$b$$$ in the tree.  Shape of rubber bands must be a simple loop. In other words, rubber band is a loop which doesn't self-intersect. Now let's define following things:   Rubber band $$$a$$$ includes rubber band $$$b$$$, if and only if rubber band $$$b$$$ is in rubber band $$$a$$$'s area, and they don't intersect each other.  Sequence of rubber bands $$$a_{1}, a_{2}, \ldots, a_{k}$$$ ($$$k \ge 2$$$) are nested, if and only if for all $$$i$$$ ($$$2 \le i \le k$$$), $$$a_{i-1}$$$ includes $$$a_{i}$$$.   This is an example of conversion. Note that rubber bands $$$5$$$ and $$$6$$$ are nested. It can be proved that is it possible to make a conversion and sequence of nested rubber bands under given constraints.What is the maximum length of sequence of nested rubber bands can be obtained from given tree? Find and print it.

Input: The first line contains integer $$$n$$$ ($$$3 \le n \le 10^{5}$$$) — the number of vertices in tree.The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$) — it means there is an edge between $$$a_{i}$$$ and $$$b_{i}$$$. It is guaranteed that given graph forms tree of $$$n$$$ vertices.

Output: Print the answer.

Note: In the first sample, you can obtain a nested sequence of $$$4$$$ rubber bands($$$1$$$, $$$2$$$, $$$5$$$, and $$$6$$$) by the conversion shown below. Of course, there are other conversions exist to make a nested sequence of $$$4$$$ rubber bands. However, you cannot make sequence of $$$5$$$ or more nested rubber bands with given tree.  You can see one of the possible conversions for the second sample below.  

Sample Inputs:
6
1 3
2 3
3 4
4 5
4 6

4
1 2
2 3
3 4

Sample Outputs:
4

2

Solution (Python):
n = int(input())
tr = [[] for i in range(n + 9)]
for i in range(n - 1):
    (u, v) = list(map(int, input().split()))
    tr[u].append(v)
    tr[v].append(u)
(dp, ans) = ([[0, 0] for i in range(n + 9)], 0)
(stk, tot) = ([(1, -1)], 0)
for i in range(n):
    (u, fa) = stk[i]
    for v in tr[u]:
        if v != fa:
            stk.append((v, u))
            tot += 1
for (u, fa) in reversed(stk):
    cnt = len(tr[u])
    for v in tr[u]:
        if v != fa:
            ans = max(ans, dp[u][1] + dp[v][0] + 1, dp[u][0] + cnt - 2 + max(dp[v]))
            dp[u] = [max(dp[u][0], max(dp[v])), max(dp[u][1], dp[v][0])]
    dp[u][0] += max(cnt - 2, 0)
    dp[u][1] += 1
    ans = max(ans, max(dp[u]))
print(ans)

Solution (Python):
import os
import sys
input = sys.stdin.buffer.readline
from collections import deque
from queue import PriorityQueue
import math
import copy

class CF(object):

    def __init__(self):
        self.n = int(input())
        self.g = [[] for _ in range(self.n)]
        self.v = [[] for _ in range(self.n)]
        self.r = []
        self.f = [-1] * self.n
        self.vis = [0] * self.n
        for _ in range(self.n - 1):
            (x, y) = list(map(int, input().split()))
            x -= 1
            y -= 1
            self.v[x].append(y)
            self.v[y].append(x)
        pass
        self.g = copy.deepcopy(self.v)
        self.dp = [[0, 0] for _ in range(self.n)]
        self.leaf = [0] * self.n
        for i in range(self.n):
            if len(self.g[i]) == 1:
                self.leaf[i] = True
        pass

    def dfs(self, root=0):
        s = [root]
        v = [self.g[root]]
        self.vis[root] = 1
        while len(s) > 0:
            if v[-1] == []:
                v.pop()
                self.r.append(s.pop())
            else:
                now = v[-1].pop()
                if not self.vis[now]:
                    self.vis[now] = 1
                    self.f[now] = s[-1]
                    s.append(now)
                    v.append(self.g[now])
        pass

    def update(self, temp, x):
        temp.append(x)
        for i in range(len(temp) - 1)[::-1]:
            if temp[i + 1] > temp[i]:
                (temp[i + 1], temp[i]) = (temp[i], temp[i + 1])
        pass
        return temp[:2]

    def main(self):
        self.dfs()
        ans = 0
        for now in self.r:
            if self.leaf[now]:
                self.dp[now][1] = 1
                self.dp[now][0] = 0
            else:
                temp = []
                t2 = []
                for to in self.v[now]:
                    if to != self.f[now]:
                        temp = self.update(temp, self.dp[to][0])
                        t2 = self.update(t2, max(self.dp[to][1], self.dp[to][0]))
                pass
                self.dp[now][1] = temp[0] + 1
                self.dp[now][0] = t2[0] + len(self.v[now]) - 1 - 1
                ans = max(ans, 1 + sum(temp))
                ans = max(ans, len(self.v[now]) - len(t2) + sum(t2))
        pass
        ar = []
        for to in self.v[0]:
            ar.append(self.dp[to][0])
        ar.sort()
        if len(ar) >= 2:
            ans = max(ans, 1 + ar[-1] + ar[-2])
        else:
            ans = max(ans, 1 + ar[-1])
        ar = []
        for to in self.v[0]:
            ar.append(max(self.dp[to][1], self.dp[to][0]))
        ar.sort()
        for i in range(len(ar) - 2):
            ar[i] = 1
        ans = max(ans, sum(ar))
        print(ans)
        pass
if __name__ == '__main__':
    cf = CF()
    cf.main()
    pass

Solution (Python):
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def print(*values, sep=' ', end='\n'):
    sep = str(sep)
    end = str(end)
    for i in range(len(values) - 1):
        sys.stdout.write(str(values[i]))
        sys.stdout.write(sep)
    if values:
        sys.stdout.write(str(values[-1]))
    sys.stdout.write(end)
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
n = int(input().decode())
C = [[] for i in range(n)]
for i in range(n - 1):
    (u, v) = map(int, input().decode().split())
    C[u - 1] += [v - 1]
    C[v - 1] += [u - 1]
start = 0
for i in range(n):
    if len(C[i]) == 1:
        start = i
        break

@bootstrap
def score(a, b):
    S = 0
    Ci = 0
    Es = a
    Ec = a
    for i in C[a]:
        if i == b:
            continue
        (s, c, es, ec) = (yield score(i, a))
        if s >= S:
            S = s
            Es = es
        if c >= S:
            S = c
            Es = ec
        if s >= Ci:
            Ci = s
            Ec = es
    Ci += 1
    S += len(C[a]) - 2
    if b == -1 or len(C[a]) == 1:
        S += 1
    yield (S, Ci, Es, Ec)
(s, c, es, ec) = score(start, -1)
if s > c:
    start = es
else:
    start = ec
(s, c, es, ec) = score(start, -1)
print(max(s, c))