| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 13309 |
| 문제명 | 트리 |
| 레벨 | 플래티넘 1 |
| 분류 |
동적 연결성 |
| 시간복잡도 | O(n+qlogn) |
| 인풋사이즈 | n<=200,000, q<=200,000 |
| 사용한 언어 | Python |
| 제출기록 | 108420KB / 3216ms |
| 최고기록 | 3216ms |
| 해결날짜 | 2021/05/24 |
"""Solution code for "BOJ 13309. 트리".
- Problem link: https://www.acmicpc.net/problem/13309
- Solution link: http://www.teferi.net/ps/problems/boj/13309
"""
import sys
from teflib import fenwicktree
from teflib import ttree
def main():
N, Q = [int(x) for x in sys.stdin.readline().split()]
tree = [[] for _ in range(N)]
for i in range(1, N):
a = int(sys.stdin.readline())
tree[a - 1].append(i)
tree[i].append(a - 1)
hld = ttree.HeavyLightDecomposition(tree, root=0)
fenwick = fenwicktree.FenwickTree(N)
for i in range(Q):
b, c, d = [int(x) for x in sys.stdin.readline().split()]
ranges = hld.get_ranges_in_path(b - 1, c - 1,
should_include_top_node=False)
is_connected = all(fenwick.query(*r) == 0 for r in ranges)
print('YES' if is_connected else 'NO')
if d == 0:
continue
u = (b - 1) if is_connected else (c - 1)
fenwick.set(hld.get_pos(u), 1)
if __name__ == '__main__':
main()
"""Solution code for "BOJ 13309. 트리".
- Problem link: https://www.acmicpc.net/problem/13309
- Solution link: http://www.teferi.net/ps/problems/boj/13309
"""
import sys
from teflib import segmenttree
from teflib import ttree
def main():
N, Q = [int(x) for x in sys.stdin.readline().split()]
tree = [[] for _ in range(N)]
for i in range(1, N):
a = int(sys.stdin.readline())
tree[a - 1].append(i)
subtree_ranges = ttree.euler_tour_technique(tree, 0)
segtree = segmenttree.LazySegmentTree(
[0] * N,
merge=lambda l, r: 0,
update_value=lambda v, p, size: max(v, p),
update_param=max)
for i in range(Q):
b, c, d = [int(x) for x in sys.stdin.readline().split()]
b_pos = subtree_ranges[b - 1][0]
c_pos = subtree_ranges[c - 1][0]
is_connected = (segtree.get(b_pos) == segtree.get(c_pos))
print('YES' if is_connected else 'NO')
if d == 1:
if is_connected:
segtree.range_update(*subtree_ranges[b - 1], b_pos)
else:
segtree.range_update(*subtree_ranges[c - 1], c_pos)
if __name__ == '__main__':
main()
"""Solution code for "BOJ 13309. 트리".
- Problem link: https://www.acmicpc.net/problem/13309
- Solution link: http://www.teferi.net/ps/problems/boj/13309
"""
import random
import sys
from teflib import fenwicktree
from teflib import ttree
def main():
N, Q = [int(x) for x in sys.stdin.readline().split()]
tree = [[] for _ in range(N)]
for i in range(1, N):
a = int(sys.stdin.readline())
tree[a - 1].append(i)
subtree_ranges = ttree.euler_tour_technique(tree, root=0)
fenwick = fenwicktree.XorFenwickTree(N + 1)
for i in range(Q):
b, c, d = [int(x) for x in sys.stdin.readline().split()]
b_group = fenwick.query(0, subtree_ranges[b - 1][0] + 1)
c_group = fenwick.query(0, subtree_ranges[c - 1][0] + 1)
is_connected = (b_group == c_group)
print('YES' if is_connected else 'NO')
if d == 1:
update_val = random.getrandbits(32)
if is_connected:
fenwick.update(subtree_ranges[b - 1][0], update_val)
fenwick.update(subtree_ranges[b - 1][1], update_val)
else:
fenwick.update(subtree_ranges[c - 1][0], update_val)
fenwick.update(subtree_ranges[c - 1][1], update_val)
if __name__ == '__main__':
main()