这道题目出自hackerrank的8月月赛的第三题。

题目大意：

先给出一棵树

之后有三种操作分别为：加边，查询，和删除一个节点

查询的时候要给出任意节点x的第k个祖先

每组数据有t个case

每个case边(P)的数量小于等于10^5

每个case的操作的数量(Q)小于等于10^5

 

题目分析：

一开始拿到这个题目的时候被搞得一头雾水，如果采用普通的暴力的办法,每一个查询需要O(P)，总体的复杂度就变成了O(Q*P)，铁定TLE…

思考了三天没有什么想法然后搜了一下，发现了这个：

研读了一番之后发现了使用一个神奇的数据结构，使得每一次的查询可以降为long(P)的复杂度，这样问题就迎刃而解了。

这个奇特的数据结构，我这样描述：

对树进行DFS，记录下每一条路径e[i]。

之后开一个node[i]标记每个节点所在的边号(index)，以及在该边的深度(depth)还有该点的“父节点”(father 该点所在边的起点e[node[i].index][0]的父节点)。

那么查询的时候Q(x,k)就等于：

k <= node[x].depth 时 return e[node[x].index][node[x].depth-k]

k > node[x].depth 时 return Q(node[x].father,k-1)

 

 

 

之后就是一系列的边界描述，不再赘述了。

第一次写出来的这个代码十分之丑陋，大家见笑了

python3写的

Level ancestorclass node:    def __init__(self,depth = 0,father = -1,index = -1,mark = -2):        self.depth = depth        self.father = father        self.index = index        self.mark = markpath = []nodes = []MAXN = 100000+5def NEW(x,y):    path.append([y,x])    l = len(path)-1    nodes[y] = node(0,-1,l,-1)    nodes[x] = node(0,y,l,1)def CON(x,y):    if (  nodes[y].mark == 1 ):        nodes[x] = node(nodes[y].depth+1,nodes[y].father,nodes[y].index,1)        nodes[y].mark = 0        path[nodes[y].index].append(x)    elif(( nodes[y].mark == -1 ) & ( len(path[nodes[y].index]) == 1 ) ):        nodes[x] = node(nodes[y].depth+1,nodes[y].father,nodes[y].index,1)        path[nodes[y].index].append(x)        else:        ADD(x)        l = len(path)-1        nodes[x] = node(0,y,l,1)def ADD(x):    path.append([x])def update(x,y):    if ( ( nodes[x].mark == -2 ) & ( nodes[y].mark == -2 ) ):        NEW(x,y)    elif ( ( nodes[x].mark == -2 ) & ( nodes[y].mark != -2 ) ):        CON(x,y)    elif ( ( nodes[x].mark != -2 ) & ( nodes[y].mark != -2 ) ):        nodes[x].father = y    elif ( ( nodes[x].mark != -2 ) & ( nodes[y].mark == -2 ) ):        ADD(y)        nodes[y] = node(0,-1,len(path)-1,1)        nodes[x].father = ydef DEL(x):    path[nodes[x].index].remove(x)    nodes[x] = node()def LOA(x,k):    if ( x == 0 ):        return 0;    if ( nodes[x].mark == -2 ):        return 0    if (nodes[x].depth >= k):        lt = nodes[x].depth - k        if ( path[nodes[x].index][0] == 0 ):            lt = lt+1        return path[nodes[x].index][lt]    if ( nodes[x].depth < k ):        if ( ( nodes[x].father == -1 ) or ( nodes[x].father == 0 ) ):            return 0        t = LOA(nodes[x].father,k-nodes[x].depth-1)        return tdef INIT():    global path    global nodes    path = []    nodes = [node() for i in range(0,MAXN)]def build():    n = int(input())    for i in range(0,n):        x,y = input().split(' ')        x = int(x)        y = int(y)        update(x,y)    #print(path)def Q():    n = int(input())    for i in range(0,n):        lt = input().split(' ')        if ( lt[0] == '0' ):            update(int(lt[2]),int(lt[1]))            #print(path)        if ( lt[0] == '1' ):            DEL(int(lt[1]))        if ( lt[0] == '2' ):            print(LOA(int(lt[1]),int(lt[2])))t = input()t = int(t)for i in range(0,t):    INIT()    build()    Q()

以后争取做到学会了就记录下来,这个代码贴给后人鄙视吧