Submission #73714907

---

Source Code Expand

from math import inf
import sys
import random

r32 = random.getrandbits(32)
r64 = random.getrandbits(64)
def input(): return sys.stdin.readline().rstrip("\r\n")
def rint(): return int(input())
def rf(): return float(input())
def rs(): return input().split()
def rmap(): return map(int, input().split())
def rmapf(): return map(float, input().split())
def rlist(): return list(map(int, input().split()))
def rlistf(): return list(map(float, input().split()))
def rmap1(): return map(lambda x: int(x)-1, input().split())
def rlist1(): return list(map(lambda x: int(x)-1, input().split()))
def fmin(a, b): return a if a < b else b
def fmax(a, b): return a if a > b else b

def exclusive(A, zero, combine, node):
    n = len(A)
    exclusiveA = [zero] * n  # Exclusive segment tree

    # Build exclusive segment tree
    for bit in range(n.bit_length())[::-1]:
        for i in range(n)[::-1]:
            # Propagate values down the segment tree
            exclusiveA[i] = exclusiveA[i // 2]
        for i in range(n & ~(bit == 0)):
            # Fold A[i] into exclusive segment tree
            ind = (i >> bit) ^ 1
            exclusiveA[ind] = combine(exclusiveA[ind], A[i], node, i)
    return exclusiveA


def rerooter(graph, default, combine, finalize=lambda nodeDP, node, eind: nodeDP):
    n = len(graph)
    rootDP = [0] * n
    forwardDP = [None] * n
    reverseDP = [None] * n

    # Compute DP for root=0
    DP = [0] * n
    bfs = [0]
    P = [0] * n
    for node in bfs:
        for nei in graph[node]:
            if P[node] != nei:
                P[nei] = node
                bfs.append(nei)

    for node in reversed(bfs):
        nodeDP = default[node]
        for eind, nei in enumerate(graph[node]):
            if P[node] != nei:
                nodeDP = combine(nodeDP, DP[nei], node, eind)
        DP[node] = finalize(nodeDP, node, graph[node].index(P[node]) if node else -1)
    # DP for root=0 done

    # Use the exclusive function to reroot
    for node in bfs:
        DP[P[node]] = DP[node]
        forwardDP[node] = [DP[nei] for nei in graph[node]]
        rerootDP = exclusive(forwardDP[node], default[node], combine, node)
        reverseDP[node] = [
            finalize(nodeDP, node, eind) for eind, nodeDP in enumerate(rerootDP)
        ]
        rootDP[node] = finalize(
            (
                combine(rerootDP[0], forwardDP[node][0], node, 0)
                if n > 1
                else default[node]
            ),
            node,
            -1,
        )
        for nei, dp in zip(graph[node], reverseDP[node]):
            DP[nei] = dp
    return rootDP, forwardDP, reverseDP




def solve():
    n = rint()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=rlist1()
        g[u].append(v)
        g[v].append(u)
        
    default = [[0,0]] * n
    
    def combine(nodeDP, childDP, node, eind):
        ret=nodeDP.copy()
        if len(g[node])>=4:
            ret[1]=max(ret[1],childDP[1]+1) 
            ret[0]=max(ret[0],childDP[1]+1)
        if len(g[node])>=3:
            ret[0]=max(ret[0],childDP[1]+1)
            ret[1]=max(ret[1],1)
        ret[0]=max(ret[0],childDP[0])
        return ret

    rootDP, forwardDP, reverseDP = rerooter(g, default, combine)
    ans=0
    for best,x in rootDP:
        ans=max(ans,best)
    print(ans)

t = 1

t = rint()

for _ in range(t):
    solve()

Submission Info

Judge Result