The Maximum Subtree (Codeforces 1238F)
Tags: DP, trees

Assume that you have $$$k$$$ one-dimensional segments $$$s_1, s_2, \dots s_k$$$ (each segment is denoted by two integers — its endpoints). Then you can build the following graph on these segments. The graph consists of $$$k$$$ vertexes, and there is an edge between the $$$i$$$-th and the $$$j$$$-th vertexes ($$$i \neq j$$$) if and only if the segments $$$s_i$$$ and $$$s_j$$$ intersect (there exists at least one point that belongs to both of them).For example, if $$$s_1 = [1, 6], s_2 = [8, 20], s_3 = [4, 10], s_4 = [2, 13], s_5 = [17, 18]$$$, then the resulting graph is the following:  A tree of size $$$m$$$ is good if it is possible to choose $$$m$$$ one-dimensional segments so that the graph built on these segments coincides with this tree.You are given a tree, you have to find its good subtree with maximum possible size. Recall that a subtree is a connected subgraph of a tree.Note that you have to answer $$$q$$$ independent queries.

Input: The first line contains one integer $$$q$$$ ($$$1 \le q \le 15 \cdot 10^4$$$) — the number of the queries. The first line of each query contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of vertices in the tree.Each of the next $$$n - 1$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) denoting an edge between vertices $$$x$$$ and $$$y$$$. It is guaranteed that the given graph is a tree.It is guaranteed that the sum of all $$$n$$$ does not exceed $$$3 \cdot 10^5$$$.

Output: For each query print one integer — the maximum size of a good subtree of the given tree.

Note: In the first query there is a good subtree of size $$$8$$$. The vertices belonging to this subtree are $$${9, 4, 10, 2, 5, 1, 6, 3}$$$.

Sample Inputs:
1
10
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10

Sample Outputs:
8

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

def bfs(s):
    q = deque()
    q.append(s)
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [-1] * (n + 1)
    p = []
    while q:
        i = q.popleft()
        p.append(i)
        for j in G[i]:
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return (parent, p)
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    G = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (x, y) = map(int, input().split())
        G[x].append(y)
        G[y].append(x)
    (parent, p) = bfs(1)
    (dp1, dp2) = ([0] * (n + 1), [0] * (n + 1))
    ans0 = 0
    while p:
        i = p.pop()
        dp1[i] += len(G[i]) - 1
        ans0 = max(ans0, dp1[i] + dp2[i] + 2)
        j = parent[i]
        if dp1[j] < dp1[i]:
            (dp1[j], dp2[j]) = (dp1[i], dp1[j])
        elif dp2[j] < dp1[i]:
            dp2[j] = dp1[i]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def weighted_dfs(n, g, root):
    seen = [None for i in range(n + 1)]
    start = [root]
    seen[root] = len(g[root]) - 1
    my_max = [0, None]
    while len(start) > 0:
        next_s = []
        for x in start:
            for y in g[x]:
                if seen[y] is None and len(g[y]) > 1:
                    seen[y] = seen[x] + len(g[y]) - 1
                    next_s.append(y)
        start = next_s
    for i in range(1, n + 1):
        if seen[i] is not None:
            my_max = max(my_max, [seen[i], i])
    return my_max

def process(n, G):
    if n == 2:
        return 2
    g = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (u, v) = G[i]
        g[u].append(v)
        g[v].append(u)
    non_leaves = []
    for i in range(1, n + 1):
        if len(g[i]) > 1:
            non_leaves.append(i)
    if len(non_leaves) == 1:
        return n
    r1 = non_leaves[0]
    (m1, m2) = weighted_dfs(n, g, r1)
    (m3, m4) = weighted_dfs(n, g, m2)
    return m3 + 2
q = int(input())
for i in range(q):
    n = int(input())
    G = []
    for j in range(n - 1):
        (u, v) = [int(x) for x in input().split()]
        G.append([u, v])
    sys.stdout.write(str(process(n, G)) + '\n')

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    ab = [list(map(int, input().split())) for i in range(n - 1)]
    graph = [[] for i in range(n + 1)]
    deg = [0] * (n + 1)
    for (a, b) in ab:
        graph[a].append(b)
        graph[b].append(a)
        deg[a] += 1
        deg[b] += 1
    pnt = [max(deg[i] - 1, 1) for i in range(n + 1)]
    root = 1
    stack = [root]
    dist = [0] * (n + 1)
    dist[root] = pnt[root]
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] == 0:
                dist[y] = dist[x] + pnt[y]
                stack.append(y)
    far = dist.index(max(dist))
    root = far
    stack = [root]
    dist = [0] * (n + 1)
    dist[root] = pnt[root]
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] == 0:
                dist[y] = dist[x] + pnt[y]
                stack.append(y)
    print(max(dist))