Brain Network (hard) (Codeforces 690C3)
Tags: Others, trees

Breaking news from zombie neurology! It turns out that – contrary to previous beliefs – every zombie is born with a single brain, and only later it evolves into a complicated brain structure. In fact, whenever a zombie consumes a brain, a new brain appears in its nervous system and gets immediately connected to one of the already existing brains using a single brain connector. Researchers are now interested in monitoring the brain latency of a zombie. Your task is to write a program which, given a history of evolution of a zombie's nervous system, computes its brain latency at every stage.

Input: The first line of the input contains one number n – the number of brains in the final nervous system (2 ≤ n ≤ 200000). In the second line a history of zombie's nervous system evolution is given. For convenience, we number all the brains by 1, 2, ..., n in the same order as they appear in the nervous system (the zombie is born with a single brain, number 1, and subsequently brains 2, 3, ..., n are added). The second line contains n - 1 space-separated numbers p2, p3, ..., pn, meaning that after a new brain k is added to the system, it gets connected to a parent-brain .

Output: Output n - 1 space-separated numbers – the brain latencies after the brain number k is added, for k = 2, 3, ..., n.


Sample Inputs:
6
1
2
2
1
5

Sample Outputs:
1 2 2 3 4

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 1)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        import math
        inf = math.inf

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = BytesIO()
                self.writable = 'x' in file.mode or 'r' not in file.mode
                self.write = self.buffer.write if self.writable else None

            def read(self):
                while True:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    if not b:
                        break
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines = 0
                return self.buffer.read()

            def readline(self):
                while self.newlines == 0:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    self.newlines = b.count(b'\n') + (not b)
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines -= 1
                return self.buffer.readline()

            def flush(self):
                if self.writable:
                    os.write(self._fd, self.buffer.getvalue())
                    (self.buffer.truncate(0), self.buffer.seek(0))

        class IOWrapper(IOBase):

            def __init__(self, file):
                self.buffer = FastIO(file)
                self.flush = self.buffer.flush
                self.writable = self.buffer.writable
                self.write = lambda s: self.buffer.write(s.encode('ascii'))
                self.read = lambda : self.buffer.read().decode('ascii')
                self.readline = lambda : self.buffer.readline().decode('ascii')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        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
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

def main():
    n = II()
    k = n.bit_length()
    parent = [[-1] * n for _ in range(k)]
    depth = [0] * n

    def search(x, y):
        if depth[x] < depth[y]:
            (x, y) = (y, x)
        res = depth[x] - depth[y]
        tmp = res
        while tmp:
            v = tmp & -tmp
            i = v.bit_length() - 1
            x = parent[i][x]
            tmp -= v
        if x == y:
            return res
        for i in range(k - 1, -1, -1):
            if parent[i][x] != parent[i][y]:
                x = parent[i][x]
                y = parent[i][y]
                res += 2 << i
        return res + 2
    (u, v) = (0, 0)
    ans = 0
    res = []
    for i in range(1, n):
        parent[0][i] = II() - 1
        for j in range(k - 1):
            if parent[j][i] == -1:
                break
            parent[j + 1][i] = parent[j][parent[j][i]]
        depth[i] = depth[parent[0][i]] + 1
        x = search(i, u)
        if x > ans:
            ans = x
            v = i
        else:
            x = search(i, v)
            if x > ans:
                ans = x
                u = i
        res.append(ans)
    print(' '.join(map(str, res)))
    return
t = 1
for _ in range(t):
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict

class SparseTable:

    def __init__(self, A, F):
        self.A = A
        self.F = F
        self.buildLG()
        self.buildST()

    def buildLG(self):
        self.LG = []
        (lg, V) = (0, 1)
        for e in range(len(self.A) + 1):
            if V * 2 <= e:
                V *= 2
                lg += 1
            self.LG.append(lg)

    def buildST(self):
        n = len(self.A)
        self.ST = []
        length = 1
        while length <= n:
            if length == 1:
                self.ST.append(self.A)
            else:
                self.ST.append([self.F(self.ST[-1][s], self.ST[-1][s + length // 2]) for s in range(n - length + 1)])
            length <<= 1

    def query(self, l, r):
        if l == r:
            return self.ST[0][l]
        if l > r:
            (l, r) = (r, l)
        e = self.LG[r - l + 1]
        return self.F(self.ST[e][l], self.ST[e][r - 2 ** e + 1])

def dfs(G, root, dst, H):
    Q = [(root, root, 0)]
    while Q:
        (e, parent, h) = Q[-1]
        if e not in H:
            H[e] = h
            dst.append((h, e))
            for x in G[e]:
                if x != parent:
                    Q.append((x, e, h + 1))
        else:
            Q.pop()
            dst.append((H[parent], parent))
n = int(input())
G = defaultdict(set)
for i in range(2, n + 1):
    e = int(input())
    G[e].add(i)
H = {}
lcaDfs = []
dfs(G, 1, lcaDfs, H)
lcaFirst = [-1] * (n + 1)
for i in range(len(lcaDfs)):
    if lcaFirst[lcaDfs[i][1]] == -1:
        lcaFirst[lcaDfs[i][1]] = i
ST = SparseTable(lcaDfs, min)
(latency, u, v) = (1, 1, 2)
L = [latency]
for e in range(3, n + 1):
    (h1, v1) = ST.query(lcaFirst[u], lcaFirst[e])
    latency1 = H[e] + H[u] - 2 * h1
    if latency1 > latency:
        latency = latency1
        (u, v) = (u, e)
    else:
        (h2, v2) = ST.query(lcaFirst[v], lcaFirst[e])
        latency2 = H[e] + H[v] - 2 * h2
        if latency2 > latency:
            latency = latency2
            (u, v) = (e, v)
    L.append(latency)
print(' '.join((str(l) for l in L)))

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict

class SparseTable:

    def __init__(self, A, F):
        self.A = A
        self.F = F
        self.buildLG()
        self.buildST()

    def buildLG(self):
        self.LG = []
        (lg, V) = (0, 1)
        for e in range(len(self.A) + 1):
            if V * 2 <= e:
                V *= 2
                lg += 1
            self.LG.append(lg)

    def buildST(self):
        n = len(self.A)
        self.ST = []
        length = 1
        while length <= n:
            if length == 1:
                self.ST.append(self.A)
            else:
                self.ST.append([self.F(self.ST[-1][s], self.ST[-1][s + length // 2]) for s in range(n - length + 1)])
            length <<= 1

    def query(self, l, r):
        if l == r:
            return self.ST[0][l]
        if l > r:
            (l, r) = (r, l)
        e = self.LG[r - l + 1]
        return self.F(self.ST[e][l], self.ST[e][r - 2 ** e + 1])

def dfs(G, root, dst, H):
    Q = [(root, root, 0)]
    while Q:
        (e, parent, h) = Q.pop()
        if e not in H:
            H[e] = h
        dst.append(e)
        dst.append(parent)
        for x in G[e]:
            if x != parent:
                Q.append((x, e, h + 1))
n = int(input())
G = defaultdict(set)
for i in range(2, n + 1):
    e = int(input())
    G[e].add(i)
H = {}
lcaDfs = []
dfs(G, 1, lcaDfs, H)
lcaFirst = [-1] * (n + 1)
for i in range(len(lcaDfs)):
    if lcaFirst[lcaDfs[i]] == -1:
        lcaFirst[lcaDfs[i]] = i
ST = SparseTable([(H[e], e) for e in lcaDfs], min)
(latency, u, v) = (1, 1, 2)
L = [latency]
for e in range(3, n + 1):
    (h1, v1) = ST.query(lcaFirst[u], lcaFirst[e])
    latency1 = H[e] + H[u] - 2 * h1
    if latency1 > latency:
        latency = latency1
        (u, v) = (u, e)
    else:
        (h2, v2) = ST.query(lcaFirst[v], lcaFirst[e])
        latency2 = H[e] + H[v] - 2 * h2
        if latency2 > latency:
            latency = latency2
            (u, v) = (e, v)
    L.append(latency)
print(' '.join((str(l) for l in L)))