Trees of Tranquillity (Codeforces 1529E)
Tags: Greedy, trees

Soroush and Keshi each have a labeled and rooted tree on $$$n$$$ vertices. Both of their trees are rooted from vertex $$$1$$$.Soroush and Keshi used to be at war. After endless decades of fighting, they finally became allies to prepare a Codeforces round. To celebrate this fortunate event, they decided to make a memorial graph on $$$n$$$ vertices.They add an edge between vertices $$$u$$$ and $$$v$$$ in the memorial graph if both of the following conditions hold:   One of $$$u$$$ or $$$v$$$ is the ancestor of the other in Soroush's tree.  Neither of $$$u$$$ or $$$v$$$ is the ancestor of the other in Keshi's tree. Here vertex $$$u$$$ is considered ancestor of vertex $$$v$$$, if $$$u$$$ lies on the path from $$$1$$$ (the root) to the $$$v$$$.Popping out of nowhere, Mashtali tried to find the maximum clique in the memorial graph for no reason. He failed because the graph was too big. Help Mashtali by finding the size of the maximum clique in the memorial graph.As a reminder, clique is a subset of vertices of the graph, each two of which are connected by an edge.

Input: The first line contains an integer $$$t$$$ $$$(1\le t\le 3 \cdot 10^5)$$$ — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ $$$(2\le n\le 3 \cdot 10^5)$$$.The second line of each test case contains $$$n-1$$$ integers $$$a_2, \ldots, a_n$$$ $$$(1 \le a_i < i)$$$, $$$a_i$$$ being the parent of the vertex $$$i$$$ in Soroush's tree.The third line of each test case contains $$$n-1$$$ integers $$$b_2, \ldots, b_n$$$ $$$(1 \le b_i < i)$$$, $$$b_i$$$ being the parent of the vertex $$$i$$$ in Keshi's tree.It is guaranteed that the given graphs are trees.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output: For each test case print a single integer — the size of the maximum clique in the memorial graph.

Note: In the first and third test cases, you can pick any vertex.In the second test case, one of the maximum cliques is $$$\{2, 3, 4, 5\}$$$.In the fourth test case, one of the maximum cliques is $$$\{3, 4, 6\}$$$.

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

Sample Outputs:
1
4
1
3

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

class bit:

    def __init__(self, n):
        self.n = n
        self.a = [0] * (n + 1)

    def add(self, idx, val):
        idx += 1
        while idx < self.n:
            self.a[idx] += val
            idx += idx & -idx

    def sumr(self, idx):
        idx += 1
        tot = 0
        while idx:
            tot += self.a[idx]
            idx -= idx & -idx
        return tot

    def sum(self, l, r):
        return self.sumr(r) - self.sumr(l - 1)

def add(i):
    bit2.add(tin[i], 1)
    bit1.add(tin[i], i)
    bit1.add(tout[i] + 1, -i)

def remove(i):
    bit2.add(tin[i], -1)
    bit1.add(tin[i], -i)
    bit1.add(tout[i] + 1, i)
for _ in range(int(input())):
    n = int(input())
    adj = [[[] for i in range(n + 1)] for j in range(2)]
    for k in range(2):
        a = list(map(int, input().split()))
        for i in range(2, n + 1):
            adj[k][a[i - 2]].append(i)
    ans = 0
    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    t = -1
    s = [1]
    visited = [0] * (n + 1)
    while s:
        c = s[-1]
        if not visited[c]:
            t += 1
            tin[c] = t
            visited[c] = 1
            for ne in adj[1][c]:
                if not visited[ne]:
                    s.append(ne)
        else:
            tout[c] = t
            s.pop()
    curr_mx = 0
    bit1 = bit(n + 1)
    bit2 = bit(n + 1)
    ops = []
    s = [1]
    visited = [0] * (n + 1)
    while s:
        c = s[-1]
        if not visited[c]:
            visited[c] = 1
            u = bit1.sumr(tin[c])
            if u:
                remove(u)
                add(c)
                ops.append([u, c])
            elif bit2.sum(tin[c], tout[c]):
                ops.append([0, 0])
            else:
                add(c)
                curr_mx += 1
                ops.append([0, c])
            ans = max(ans, curr_mx)
            for ne in adj[0][c]:
                if not visited[ne]:
                    s.append(ne)
        else:
            (u, v) = ops.pop()
            if u:
                add(u)
                curr_mx += 1
            if v:
                remove(v)
                curr_mx -= 1
            s.pop()
    print(ans)

Solution (Python):
class bit:

    def __init__(self, n):
        self.n = n
        self.a = [0] * (n + 1)

    def add(self, idx, val):
        idx += 1
        while idx < self.n:
            self.a[idx] += val
            idx += idx & -idx

    def sumr(self, idx):
        idx += 1
        tot = 0
        while idx:
            tot += self.a[idx]
            idx -= idx & -idx
        return tot

    def sum(self, l, r):
        return self.sumr(r) - self.sumr(l - 1)

def add(i):
    bit2.add(tin[i], 1)
    bit1.add(tin[i], i)
    bit1.add(tout[i] + 1, -i)

def remove(i):
    bit2.add(tin[i], -1)
    bit1.add(tin[i], -i)
    bit1.add(tout[i] + 1, i)
for _ in range(int(input())):
    n = int(input())
    adj = [[[] for i in range(n + 1)] for j in range(2)]
    for k in range(2):
        a = list(map(int, input().split()))
        for i in range(2, n + 1):
            adj[k][a[i - 2]].append(i)
    ans = 0
    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    t = -1
    s = [1]
    visited = [0] * (n + 1)
    while s:
        c = s[-1]
        if not visited[c]:
            t += 1
            tin[c] = t
            visited[c] = 1
            s += [ne for ne in adj[1][c] if not visited[ne]]
        else:
            tout[c] = t
            s.pop()
    curr_mx = 0
    bit1 = bit(n + 1)
    bit2 = bit(n + 1)
    ops = []
    s = [1]
    visited = [0] * (n + 1)
    while s:
        c = s[-1]
        if not visited[c]:
            visited[c] = 1
            u = bit1.sumr(tin[c])
            if u:
                remove(u)
                add(c)
                ops.append([u, c])
            elif bit2.sum(tin[c], tout[c]):
                ops.append([0, 0])
            else:
                add(c)
                curr_mx += 1
                ops.append([0, c])
            ans = max(ans, curr_mx)
            s += [ne for ne in adj[0][c] if not visited[ne]]
        else:
            (u, v) = ops.pop()
            if u:
                add(u)
                curr_mx += 1
            if v:
                remove(v)
                curr_mx -= 1
            s.pop()
    print(ans)

Solution (Python):
class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

class OrderedList(SortedList):

    def __init__(self, arg):
        super().__init__(arg)

    def rangeCountByValue(self, leftVal, rightVal):
        leftCummulative = self.bisect_left(leftVal)
        rightCummulative = self.bisect_left(rightVal + 1)
        return rightCummulative - leftCummulative
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

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        sa = readIntArr()
        sk = readIntArr()
        Sadj = [[] for _a in range(n + 1)]
        Kadj = [[] for _a in range(n + 1)]
        for i in range(n - 1):
            u = i + 2
            vS = sa[i]
            Sadj[vS].append(u)
            vK = sk[i]
            Kadj[vK].append(u)
        KeshiTimeIn = [-1] * (n + 1)
        KeshiTimeOut = [-1] * (n + 1)
        time = [0]

        @bootstrap
        def KeshiEulerTour(node):
            KeshiTimeIn[node] = time[0]
            time[0] += 1
            for nex in Kadj[node]:
                yield KeshiEulerTour(nex)
            KeshiTimeOut[node] = time[0]
            time[0] += 1
            yield None
        KeshiEulerTour(1)
        getTimeOut = [-1] * (n * 2 + 5)
        for node in range(1, n + 1):
            getTimeOut[KeshiTimeIn[node]] = KeshiTimeOut[node]
        maxSize = [0]
        group = OrderedList([])

        @bootstrap
        def dfs(node):
            tempStore = []
            nodeTIn = KeshiTimeIn[node]
            nodeTOut = KeshiTimeOut[node]
            prevNodeIdx = group.bisect_left(nodeTIn) - 1
            nextNodeIdx = prevNodeIdx + 1
            hasDescendantInKeshiSubtree = False
            hasAncestorInKeshiSubtree = False
            if prevNodeIdx >= 0:
                tOutMax = getTimeOut[group[prevNodeIdx]]
                if tOutMax > nodeTOut:
                    hasAncestorInKeshiSubtree = True
                    tempStore.append(group.pop(prevNodeIdx))
                    nextNodeIdx -= 1
            if hasAncestorInKeshiSubtree == False and nextNodeIdx < len(group):
                tOutMin = getTimeOut[group[nextNodeIdx]]
                if tOutMin < nodeTOut:
                    hasDescendantInKeshiSubtree = True
            if hasDescendantInKeshiSubtree == False:
                group.add(nodeTIn)
            maxSize[0] = max(maxSize[0], len(group))
            for nex in Sadj[node]:
                yield dfs(nex)
            if hasDescendantInKeshiSubtree == False:
                group.remove(nodeTIn)
            for x in tempStore:
                group.add(x)
            yield None
        dfs(1)
        allans.append(maxSize[0])
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
    main()