📝 문제 정보#
🧐 관찰 및 접근#
- dfs를 돌리듯이 지금까지 걸어온 과정들을 기록하면서 다음 노드를 갈 수 있었는가?를 체크하자.
💻 풀이#
- 코드 (C++):
import sys
input = sys.stdin.readline
N = int(input())
links = [set() for _ in range(N + 1)]
for _ in range(N-1):
a, b = map(int, input().split())
links[a].add(b)
links[b].add(a)
lst = list(map(int, input().split()))
if lst[0] != 1:
print(0)
exit()
nidx = 1
stk = [1]
while nidx < N:
if not stk:
print(0)
exit()
cur = stk[-1]
if lst[nidx] in links[cur]:
stk.append(lst[nidx])
nidx += 1
else:
stk.pop()
print(1)