题目出处
这道题目出自hackerrank的8月月赛的第三题。
题目大意：
先给出一棵树
之后有三种操作分别为：加边，查询，和删除一个节点
查询的时候要给出任意节点x的第k个祖先
每组数据有t个case
每个case边(P)的数量小于等于10^5
每个case的操作的数量(Q)小于等于10^5
题目分析：
一开始拿到这个题目的时候被搞得一头雾水，如果采用普通的暴力的办法,每一个查询需要O(P)，总体的复杂度就变成了O(Q*P)，铁定TLE…
思考了三天没有什么想法然后搜了一下，发现了这个：
Level ancestor problem
研读了一番之后发现了使用一个神奇的数据结构，使得每一次的查询可以降为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 = mark
path = []
nodes = []
MAXN = 100000+5
def 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 = y
def 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 t
def 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()
以后争取做到学会了就记录下来,这个代码贴给后人鄙视吧