AtCoder Regular Contest 095 - Permutation Tree

Takahashi has an ability to generate a tree using a permutation (p_1,p_2,...,p_n) of (1,2,...,n), in the following process:
First, prepare Vertex 1, Vertex 2, ..., Vertex N.
For each i=1,2,...,n, perform the following operation:
 - If p_i = 1, do nothing.
 - If p_i \neq 1, let j' be the largest j such that p_j < p_i. Span an edge between Vertex i and Vertex j'.
Takahashi is trying to make his favorite tree with this ability.
His favorite tree has n vertices from Vertex 1 through Vertex n, and its i-th edge connects Vertex v_i and w_i.
Determine if he can make a tree isomorphic to his favorite tree by using a proper permutation.
If he can do so, find the lexicographically smallest such permutation.

-----Notes-----
For the definition of isomorphism of trees, see wikipedia. Intuitively, two trees are isomorphic when they are the "same" if we disregard the indices of their vertices.

-----Constraints-----
 - 2 \leq n \leq 10^5
 - 1 \leq v_i, w_i \leq n
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
n
v_1 w_1
v_2 w_2
:
v_{n-1} w_{n-1}

-----Output-----
If there is no permutation that can generate a tree isomorphic to Takahashi's favorite tree, print -1.
If it exists, print the lexicographically smallest such permutation, with spaces in between.

-----Sample Input-----
6
1 2
1 3
1 4
1 5
5 6

-----Sample Output-----
1 2 4 5 3 6

If the permutation (1, 2, 4, 5, 3, 6) is used to generate a tree, it looks as follows:

This is isomorphic to the given graph.

Difficulty: VERY_HARD

Starter code:

Solutions:
import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
n = II()
to = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = MI1()
	to[u].append(v)
	to[v].append(u)

def far(u):
	stack = [(u, -1, 0)]
	mxd = mxu = -1
	while stack:
		(u, pu, d) = stack.pop()
		if d > mxd:
			mxd = d
			mxu = u
		for v in to[u]:
			if v == pu:
				continue
			stack.append((v, u, d + 1))
	return (mxu, mxd)
(s, _) = far(0)
(t, dist) = far(s)

def makepath(u, t):
	stack = [(u, -1)]
	while stack:
		(u, pu) = stack.pop()
		while path and path[-1] != pu:
			path.pop()
		path.append(u)
		if u == t:
			return
		for v in to[u]:
			if v == pu:
				continue
			stack.append((v, u))
path = [s]
makepath(s, t)
leg = []
for u in path[1:-1]:
	leg.append(len(to[u]) - 2)
if sum(leg) + dist + 1 != n:
	print(-1)
	return
ans = []
ans.append(1)
u = 2
for l in leg:
	for v in range(u + 1, u + 1 + l):
		ans.append(v)
	ans.append(u)
	u += l + 1
ans.append(u)
leg.reverse()
ans2 = []
ans2.append(1)
u = 2
for l in leg:
	for v in range(u + 1, u + 1 + l):
		ans2.append(v)
	ans2.append(u)
	u += l + 1
ans2.append(u)
if ans2 < ans:
	ans = ans2
print(*ans)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
N = int(input())
VW = [[int(x) - 1 for x in input().split()] for _ in range(N - 1)]
graph = [[] for _ in range(N)]
deg = [0] * N
for (v, w) in VW:
	graph[v].append(w)
	graph[w].append(v)
	deg[v] += 1
	deg[w] += 1

def dijkstra(start):
	INF = 10 ** 10
	dist = [INF] * N
	q = [(start, 0)]
	while q:
		qq = []
		for (v, d) in q:
			dist[v] = d
			for w in graph[v]:
				if dist[w] == INF:
					qq.append((w, d + 1))
		q = qq
	return dist
dist = dijkstra(0)
v = dist.index(max(dist))
dist = dijkstra(v)
w = dist.index(max(dist))
diag = (v, w)

def create_perm(start):
	arr = []
	v = start
	parent = None
	next_p = 1
	while True:
		n = 0
		next_v = None
		for w in graph[v]:
			if w == parent:
				continue
			if next_v is None or deg[next_v] < deg[w]:
				next_v = w
			if deg[w] == 1:
				n += 1
		if next_v is None:
			return arr + [next_p]
		if deg[next_v] == 1:
			n -= 1
		arr += list(range(next_p + 1, next_p + n + 1))
		arr.append(next_p)
		next_p += n + 1
		parent = v
		v = next_v
P = create_perm(diag[1])
Q = create_perm(diag[0])
if len(P) != N:
	answer = -1
else:
	if P > Q:
		P = Q
	answer = ' '.join(map(str, P))
print(answer)


def solve(n, adj_list, d):
	s = []
	path_adj_list = [[] for _ in range(n)]
	for v in range(n):
		if 1 < d[v]:
			p = path_adj_list[v]
			for w in adj_list[v]:
				if 1 < d[w]:
					p.append(w)
			if 2 < len(p):
				print(-1)
				return
			if len(p) == 1:
				s.append(v)
	if len(s) == 0:
		ans = [1] + [v for v in range(3, n)] + [2]
		if 2 < n:
			ans += [n]
		print(' '.join(list(map(str, ans))))
		return
	visited = [False] * n
	(v, w) = s
	while v != w and d[v] == d[w]:
		visited[v] = True
		visited[w] = True
		f = False
		for nv in path_adj_list[v]:
			if not visited[nv]:
				f = True
				v = nv
				break
		if not f:
			break
		f = False
		for nw in path_adj_list[w]:
			if not visited[nw]:
				f = True
				w = nw
				break
		if not f:
			break
	if d[v] > d[w]:
		v = s[1]
	else:
		v = s[0]
	visited = [False] * n
	visited[v] = True
	ans = [1] + [w for w in range(3, d[v] + 1)] + [2]
	c = d[v]
	v = path_adj_list[v][0]
	while True:
		visited[v] = True
		ans += [w for w in range(c + 2, c + d[v])] + [c + 1]
		c += d[v] - 1
		f = False
		for nv in path_adj_list[v]:
			if not visited[nv]:
				f = True
				v = nv
				break
		if not f:
			break
	ans += [n]
	print(' '.join(list(map(str, ans))))
	return

def main():
	n = input()
	n = int(n)
	adj_list = [[] for _ in range(n)]
	d = [0] * n
	for _ in range(n - 1):
		(v, w) = input().split()
		v = int(v) - 1
		w = int(w) - 1
		adj_list[v].append(w)
		adj_list[w].append(v)
		d[v] += 1
		d[w] += 1
	solve(n, adj_list, d)
main()


import sys
from collections import deque

def diameter(n, links):
	q = deque([(0, -1)])
	v = 0
	while q:
		(v, p) = q.popleft()
		q.extend(((u, v) for u in links[v] if u != p))
	q = deque([(v, -1)])
	w = 0
	parents = [-1] * n
	while q:
		(w, p) = q.popleft()
		parents[w] = p
		q.extend(((u, w) for u in links[w] if u != p))
	parents_rev = [-1] * n
	p = w
	while parents[p] != -1:
		parents_rev[parents[p]] = p
		p = parents[p]
	return (v, w, parents, parents_rev)

def construct(s, links, parents, parents_rev):
	v = s
	result = []
	while v != -1:
		(pv, rv) = (parents[v], parents_rev[v])
		child_count = 0
		for u in links[v]:
			if u == pv or u == rv:
				continue
			if len(links[u]) != 1:
				return False
			child_count += 1
		my_value = len(result) + 1
		result.extend(range(my_value + 1, my_value + child_count + 1))
		result.append(my_value)
		v = parents[v]
	return result

def solve(n, links):
	(d1, d2, parents, parents_rev) = diameter(n, links)
	result1 = construct(d1, links, parents_rev, parents)
	if result1 is False:
		return [-1]
	result2 = construct(d2, links, parents, parents_rev)
	return min(result1, result2)
n = int(input())
links = [set() for _ in range(n)]
INF = 10 ** 9
for line in sys.stdin:
	(v, w) = map(int, line.split())
	v -= 1
	w -= 1
	links[v].add(w)
	links[w].add(v)
print(*solve(n, links))


import sys
readline = sys.stdin.readline

def parorder(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[p] = -1
	stack = [p]
	order = []
	visited = set([p])
	ast = stack.append
	apo = order.append
	while stack:
		vn = stack.pop()
		apo(vn)
		for vf in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			ast(vf)
	return (par, order)

def getcld(p):
	res = [[] for _ in range(len(p))]
	for (i, v) in enumerate(p[1:], 1):
		res[v].append(i)
	return res

def dfs(St):
	dist = [0] * N
	stack = St[:]
	used = [False] * N
	for s in St:
		used[s] = True
	while stack:
		vn = stack.pop()
		for vf in Edge[vn]:
			if not used[vf]:
				used[vf] = True
				dist[vf] = 1 + dist[vn]
				stack.append(vf)
	return dist
N = int(readline())
Edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge[a].append(b)
	Edge[b].append(a)
dist0 = dfs([0])
fs = dist0.index(max(dist0))
distfs = dfs([fs])
en = distfs.index(max(distfs))
disten = dfs([en])
Dia = distfs[en]
path = []
for i in range(N):
	if distfs[i] + disten[i] == Dia:
		path.append(i)
if max(dfs(path)) > 1:
	print(-1)
else:
	path.sort(key=lambda x: distfs[x])
	cnt = 1
	hold = 0
	perm1 = [None] * N
	onpath = set(path)
	idx = 0
	for i in range(Dia + 1):
		vn = path[i]
		hold = 0
		for vf in Edge[vn]:
			if vf in onpath:
				continue
			hold += 1
			perm1[idx] = cnt + hold
			idx += 1
		perm1[idx] = cnt
		idx += 1
		cnt = cnt + hold + 1
	cnt = 1
	hold = 0
	perm2 = [None] * N
	onpath = set(path)
	idx = 0
	for i in range(Dia + 1):
		vn = path[Dia - i]
		hold = 0
		for vf in Edge[vn]:
			if vf in onpath:
				continue
			hold += 1
			perm2[idx] = cnt + hold
			idx += 1
		perm2[idx] = cnt
		idx += 1
		cnt = cnt + hold + 1
	print(*min(perm1, perm2))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10 ** 5)
n = int(input())
edge = [[] for i in range(n)]
for i in range(n - 1):
	(v, w) = map(int, input().split())
	edge[v - 1].append(w - 1)
	edge[w - 1].append(v - 1)
if n == 2:
	print(1, 2)
	return
leafcnt = [0] * n
for v in range(n):
	for nv in edge[v]:
		if len(edge[nv]) == 1:
			leafcnt[v] += 1
used = [False] * n
line = []

def line_check(v):
	used[v] = True
	line.append(leafcnt[v])
	flag = False
	for nv in edge[v]:
		if not used[nv] and len(edge[nv]) != 1:
			if not flag:
				line_check(nv)
				flag = True
			else:
				return False
	return True
for v in range(n):
	if not used[v] and len(edge[v]) - leafcnt[v] <= 1 and (len(edge[v]) != 1):
		if not line:
			check = line_check(v)
			if not check:
				print(-1)
				return ()
		else:
			print(-1)
			return ()
line_rev = line[::-1]
res = min(line, line_rev)
res = [0] + res + [0]
res[1] -= 1
res[-2] -= 1
ans = []
L = 1
for val in res:
	R = L + val
	for i in range(L + 1, R + 1):
		ans.append(i)
	ans.append(L)
	L = R + 1
print(*ans)