Problem:

Problem F: Marked Ancestor

You are given a tree T that consists of N nodes. Each node is numbered from 1 to N, and node 1 is always the root node of T. Consider the following two operations on T:

    
M v: (Mark) Mark node v.

    
Q v: (Query) Print the index of the nearest marked ancestor of node v which is nearest to it. Initially, only the root node is marked. Note that a node is an ancestor of itself.

Your job is to write a program that performs a sequence of these operations on a given tree and calculates
the value that each Q operation will print. To avoid too large output file, your program is requested to
print the sum of the outputs of all query operations. Note that the judges confirmed that it is possible to
calculate every output of query operations in a given sequence.

Input

The input consists of multiple datasets. Each dataset has the following format:

The first line of the input contains two integers N and Q, which denotes the number of nodes in the tree
T and the number of operations, respectively. These numbers meet the following conditions: 1 ≤ N ≤ 100000 and 1 ≤ Q ≤ 100000.

The following N - 1 lines describe the configuration of the tree T. Each line contains a single integer pi (i = 2, ... , N), which represents the index of the parent of i-th node.

The next Q lines contain operations in order. Each operation is formatted as "M v" or "Q v", where v is the index of a node.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the sum of the outputs of all query operations in one line.

Sample Input

6 3
1
1
2
3
3
Q 5
M 3
Q 5
0 0

Output for the Sample Input

4



Sample input:
6 3
1
1
2
3
3
Q 5
M 3
Q 5
0 0


Sample output:
4

Submission status: Wrong Answer

Solution code:
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


while True:
    N, Q = map(int, input().split())
    if N == Q == 0:
        break
    parents = [-1] + [int(input()) - 1 for _ in range(N - 1)]
    queries = []
    marked = set()
    for _ in range(Q):
        k, v = input().split()
        v = int(v) - 1
        queries.append((k, v))
        if k == "M":
            marked.add(v)
    uf = UnionFindTree(N)
    for i in range(1, N):
        if i not in marked:
            p_root = uf.find(parents[i])
            uf.par[i] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[i] + 1)
    ans = 0
    for k, v in reversed(queries):
        if k == "Q":
            ans += uf.find(v)
        elif not uf.same(v, parents[v]):
            p_root = uf.find(parents[i])
            uf.par[i] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[i] + 1)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


while True:
    N, Q = map(int, input().split())
    if N == Q == 0:
        break
    parents = [-1] + [int(input()) - 1 for _ in range(N - 1)]
    queries = []
    marked = set()
    for _ in range(Q):
        k, v = input().split()
        v = int(v) - 1
        queries.append((k, v))
        if k == "M":
            marked.add(v)
    uf = UnionFindTree(N)
    for i in range(1, N):
        if i not in marked:
            p_root = uf.find(parents[i])
            uf.par[i] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[i] + 1)
    ans = 0
    for k, v in reversed(queries):
        if k == "Q":
            ans += uf.find(v) + 1
        elif not uf.same(v, parents[v]):
            p_root = uf.find(parents[v])
            uf.par[v] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[v] + 1)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


while True:
    N, Q = map(int, input().split())
    if N == Q == 0:
        break
    parents = [0] + [int(input()) - 1 for _ in range(N - 1)]
    queries = []
    marked = set()
    for _ in range(Q):
        k, v = input().split()
        v = int(v) - 1
        queries.append((k, v))
        if k == "M":
            marked.add(v)
    uf = UnionFindTree(N)
    for i in range(1, N):
        if i not in marked:
            p_root = uf.find(parents[i])
            uf.par[i] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[i] + 1)
    ans = 0
    for k, v in reversed(queries):
        if k == "Q":
            ans += uf.find(v) + 1
        elif not uf.same(v, parents[v]):
            p_root = uf.find(parents[v])
            uf.par[v] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[v] + 1)
    print(ans)

Submission status: Wrong Answer

Solution code:
marked = []
par = []
rank = []

def find(x):
    if par[x] == x:
        return x
    else:
        if marked[x]:
            return x
        return find(par[x])

def main():
    global marked, par, rank
    n,q = [int(i) for i in input().split()]
    marked = [False for i in range(n+1)]
    par = [ i for i in range(n+1)]
    rank = [ 0 for i in range(n+1)]
    ans = 0
    for i in range(2,n+1):
        par[i] = int(input())
    for i in range(q):
        s = input().split()
        if s[0] == 'Q':
            ans += find(int(s[1]))
        else:
            marked[int(s[1])]=True
    input()
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
marked = []
par = []
rank = []

def find(x):
    if par[x] == x:
        return x
    else:
        if marked[x]:
            return x
        return find(par[x])

def main():
    global marked, par, rank
    n,q = [int(i) for i in input().split()]
    marked = [False for i in range(n+1)]
    par = [ i for i in range(n+1)]
    rank = [ 0 for i in range(n+1)]
    ans = 0
    for i in range(2,n+1):
        par[i] = int(input())
    for i in range(q):
        s = input().split()
        if s[0] == 'Q':
            ans += find(int(s[1]))
        else:
            marked[int(s[1])]=True
    print(ans)
    input()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
marked = []
par = []
rank = []

def find(x):
    if par[x] == x:
        return x
    else:
        if marked[x]:
            return x
        return find(par[x])

def main():
    global marked, par, rank
    n,q = [int(i) for i in input().split()]
    marked = [False for i in range(n+1)]
    par = [ i for i in range(n+1)]
    rank = [ 0 for i in range(n+1)]
    ans = 0
    for i in range(2,n+1):
        par[i] = int(input())
    for i in range(q):
        s = input().split()
        if s[0] == 'Q':
            ans += find(int(s[1]))
        else:
            marked[int(s[1])]=True
    print(ans)
    input()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
marked = []
par = []
rank = []

def find(x):
    if par[x] == x:
        return x
    else:
        if marked[x]:
            return x
        return find(par[x])

def main():
    global marked, par, rank
    n,q = [int(i) for i in input().split()]
    marked = [False for i in range(n+1)]
    par = [ i for i in range(n+1)]
    rank = [ 0 for i in range(n+1)]
    ans = 0
    for i in range(2,n+1):
        par[i] = int(input())
    for i in range(q):
        s = input().split()
        if s[0] == 'Q':
            print(find(int(s[1])))
        else:
            marked[int(s[1])]=True
    input()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


while True:
    N, Q = map(int, input().split())
    if N == Q == 0:
        break
    parents = [0] + [int(input()) - 1 for _ in range(N - 1)]
    queries = []
    marked = set()
    for _ in range(Q):
        k, v = input().split()
        v = int(v) - 1
        if k == "Q":
            queries.append((k, v))
        elif k == "M" and v not in marked:
            marked.add(v)
            queries.append((k, v))

    uf = UnionFindTree(N)
    for i in range(1, N):
        if i not in marked:
            p_root = uf.find(parents[i])
            uf.par[i] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[i] + 1)
    ans = 0
    for k, v in reversed(queries):
        if k == "Q":
            ans += uf.find(v) + 1
        elif not uf.same(v, parents[v]):
            p_root = uf.find(parents[v])
            uf.par[v] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[v] + 1)
    print(ans)

Submission status: Accepted

Solution code:
def solve():
    import sys
    file_input = sys.stdin
    while True:
        N, Q = map(int, file_input.readline().split())
        if N == 0:
            break
        parent = [None, None]
        parent += [int(file_input.readline()) for _ in range(N - 1)]
        unmarked = [True] * (N + 1)
        unmarked[1] = False
        ans = 0
        for _ in range(Q):
            line = file_input.readline()
            v = int(line[2:])
            if line[0] == 'M':
                unmarked[v] = False
            else:
                while unmarked[v]:
                    v = parent[v]
                ans += v
        print(ans)

solve()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.table = [None] * size

    def find(self, x):
        if self.table[x] == None:
            return x
        else:
            # compression of the path
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    
    def union(self, parent, child):
        p_root = self.find(parent)
        c_root = self.find(child)
        if p_root != c_root:
            self.table[c_root] = p_root
        
def solve():
    import sys
    input_lines = sys.stdin.readlines()
    while True:
        N, Q = map(int, input_lines[0].split())
        if N == 0:
            break
        
        unmarked = [True] * (N + 1)
        unmarked[1] = False
        operation = []
        for o in input_lines[N:N+Q]:
            mq, v = o.split()
            v = int(v)
            if mq == 'M':
                if unmarked[v]:
                    unmarked[v] = False
                    operation.append((mq, v))
            else:
                operation.append((mq, v))
        
        uf = UnionFind(N + 1)
        parent = [None, 1] + list(map(int, input_lines[1:N]))
        for v, p in enumerate(parent[2:], start=2):
            if unmarked[v]:
                uf.union(p, v)
        
        ans = 0
        for o, v in reversed(operation):
            if o == 'M':
                uf.union(parent[v], v)
            else:
                ans += uf.find(v)
        
        print(ans)
        
        del input_lines[:N+Q]

solve()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.table = [None] * size

    def find(self, x):
        if self.table[x] == None:
            return x
        else:
            # compression of the path
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    
    def union(self, parent, child):
        p_root = self.find(parent)
        c_root = self.find(child)
        if p_root != c_root:
            self.table[c_root] = p_root
        
def solve():
    import sys
    input_lines = sys.stdin.readlines()
    while True:
        N, Q = map(int, input_lines[0].split())
        if N == 0:
            break
        
        parent = [0, 1] + list(map(int, input_lines[1:N]))
        
        unmarked = [True] * (N + 1)
        unmarked[1] = False
        operation = []
        for o in input_lines[N:N+Q]:
            mq, v = o.split()
            v = int(v)
            if mq == 'M':
                if unmarked[v]:
                    unmarked[v] = False
                    operation.append((mq, v))
            else:
                operation.append((mq, v))
        
        uf = UnionFind(N + 1)
        for v, p in enumerate(parent[2:], start=2):
            if unmarked[v]:
                uf.union(p, v)
        
        ans = 0
        for mq, v in reversed(operation):
            if mq == 'M':
                uf.union(parent[v], v)
            else:
                ans += uf.find(v)
        
        print(ans)
        
        del input_lines[:N+Q]

solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n

    def find(self,x): #根を見つける、繋ぎ直す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def unite(self,x,y):
        y = self.find(y)
        x = self.find(x)
        self.parents[y] += self.parents[x]
        self.parents[x] = y
    
    def same(self,x,y):#xとyが同じグループにいるか判定
        return self.find(x) == self.find(y)


def solve(N,Q):
    parents = [-1] * N
    for i in range(1,N):
        p = int(input()) - 1
        parents[i] = p
    
    query = []
    mark = [0] * N
    mark[0] = 1
    for _ in range(Q):
        q = input().split()
        v = int(q[1]) - 1
        if q[0] == 'M':
            mark[v] += 1
            query.append((0,v))
        else:
            query.append((1,v))
    
    uf = UnionFind(N)
    for i in range(N):
        if mark[i] == 0:
            uf.unite(i,parents[i])
    
    ans = 0
    for ty,v in query[::-1]:
        if ty == 0:
            mark[v] -= 1
            if mark[v] == 0:
                uf.unite(v,parents[v])
        else:
            ans += uf.find(v) + 1
    print(ans)

def main():
    while True:
        N,M = map(int,input().split())
        if N == 0:
            return
        solve(N,M)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

    def same(self, x, y):
        return self.find(x) == self.find(y)


while True:
    N, Q = map(int, input().split())
    if N == Q == 0:
        break
    parent = [0, 1] + [int(input()) for i in range(2, N+1)]
    queries = []
    marked = set([1])
    for i in range(Q):
        o, v = input().split()
        v = int(v)
        if o == 'M':
            if v in marked:
                continue
            marked.add(v)
        queries.append((o, v))

    uf = UnionFind(N+1)
    for i in range(1, N+1):
        if i not in marked:
            uf.unite(i, parent[i])

    ans = 0
    for o, v in reversed(queries):
        if o == 'M':
            uf.unite(v, parent[v])
        else:
            ans += uf.find(v)

    print(ans)

Submission status: Accepted

Solution code:
def root(x):
    while P[x-1]!=x:
        x = P[x-1]
    return x

def mark(x):
    P[x-1] = x

while True:
    n,q = map(int,input().split())
    res = 0
    if n==0:
        break
    P = [1]
    for _ in range(n-1):
        P.append(int(input()))
    
    for _ in range(q):
        com,num=map(str,input().split())
        if com == "Q":
            res += root(int(num))
        else:
            mark(int(num))
    print(res)

Submission status: Accepted

Solution code:
def root(x):
    while P[x] != x:
        x = P[x]
    return x
def mark(x):
    P[x-1] = x-1
def query(x):
    v = root(x-1) +1
    return v

while True:
    N,Q = map(int,input().strip().split(" "))
    if N == Q == 0:
        break
    P = []
    P.append(0)
    for i in range(N-1):
        p_i = int(input().strip()) -1
        P.append(p_i)
    s = 0
    for j in range(Q):
        op = input().strip().split(" ")
        if op[0] == "M":
            mark(int(op[1]))
        else:
            s += query(int(op[1]))
    print(s)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] += self.table[s1]
            self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    rr = []

    def f(n,q):
        ps = [0, 1] + [I() for _ in range(n-1)]
        qs = []
        ms = set()
        for i in range(q):
            s,t = LS()
            t = int(t)
            if s == 'M':
                if t in ms:
                    continue
                ms.add(t)
            qs.append((s,t))
        uf = UnionFind(n+1)
        for i in range(2,n+1):
            if i in ms:
                continue
            uf.union(i, ps[i])

        r = 0
        for s,t in qs[::-1]:
            if s == 'Q':
                r += uf.find(t)
            else:
                uf.union(t, ps[t])

        return r

    while 1:
        n,q = LI()
        if n == 0 and q == 0:
            break
        rr.append(f(n,q))

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


while True:
    N, Q = map(int, input().split())
    if N == Q == 0:
        break
    parents = [-1] + [int(input()) - 1 for _ in range(N - 1)]
    queries = []
    marked = set()
    for _ in range(Q):
        k, v = input().split()
        v = int(v) - 1
        queries.append((k, v))
        if k == "M":
            marked.add(v)
    uf = UnionFindTree(N)
    for i in range(1, N):
        if i not in marked:
            p_root = uf.find(parents[i])
            uf.par[i] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[i] + 1)
    ans = 0
    for k, v in reversed(queries):
        if k == "Q":
            ans += uf.find(v) + 1
        elif not uf.same(v, parents[v]):
            p_root = uf.find(parents[v])
            uf.par[v] = p_root
            uf.rank[p_root] = max(uf.rank[p_root], uf.par[v] + 1)
    print(ans)

Submission status: Runtime Error

Solution code:
def solve():
    import sys
    file_input = sys.stdin
    
    def marked_ancestor(v):
        if v == ancestor[v]:
            return v
        else:
            ancestor[v] = marked_ancestor(parent[v])
            return ancestor[v]
    
    def line_ans(line):
        v = int(line[2:])
        if line[0] == 'M':
            ancestor[v] = v
            return 0
        else:
            return marked_ancestor(v)
    
    while True:
        N, Q = map(int, file_input.readline().split())
        if N == 0:
            break
        parent = [None, None]
        parent += [int(file_input.readline()) for _ in range(N - 1)]
        ancestor = [1] * (N + 1)
        ans = (line_ans(file_input.readline()) for _ in range(Q))
        print(sum(ans))

solve()