Calculate! 2

• XOR 문제에 오일러 투어 테크닉을 결합한 문제.
• 그냥 오일러 투어 테크닉으로 트리를 편 뒤에, 구간 xor 업데이트/xor 쿼리를 처리해주기만 하면 되는 문제라서 특별히 언급할 것이 없다.
• 오일러 트리 테크닉과 구간 xor 업데이트/xor 쿼리 는 각각 링크를 참고. 이 문제도 XOR에서 처럼 lazy propagation으로 문제를 풀려고 하면 python으로는 시간 초과가 난다. Python으로 통과하려면 두개의 Fenwick tree를 이용해서 처리하는 테크닉을 사용해야 한다.
• 시간 복잡도는 오일러 트리 테크닉에 O(n), fenwick tree를 구축한 뒤 구간 xor 업데이트/xor 쿼리를 처리하는데에 O(n+mlogn). 합치면 O(n+mlogn)

"""Solution code for "BOJ 15782. Calculate! 2".

- Problem link: https://www.acmicpc.net/problem/15782
- Solution link: http://www.teferi.net/ps/problems/boj/15782
"""

import sys
from teflib import fenwicktree
from teflib import tgraph


def euler_tour_technique(tree, root, values):
    values_in_dfs_order = []
    subtree_ranges = [[None, None] for _ in tree]
    for node in tgraph.dfs(tree, root, yields_on_leave=True):
        if subtree_ranges[node][0] is None:
            subtree_ranges[node][0] = len(values_in_dfs_order)
            values_in_dfs_order.append(values[node])
        else:
            subtree_ranges[node][1] = len(values_in_dfs_order)
    return values_in_dfs_order, subtree_ranges


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    tree = [[] for _ in range(N)]
    for _ in range(N - 1):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        tree[A - 1].append(B - 1)
        tree[B - 1].append(A - 1)
    nums = [int(x) for x in sys.stdin.readline().split()]
    nums_in_dfs_order, subtree_ranges = euler_tour_technique(tree, 0, nums)
    fenwick1 = fenwicktree.XorFenwickTree(N + 1)
    fenwick2 = fenwicktree.XorFenwickTree(nums_in_dfs_order + [0])
    for _ in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            x = query[1]
            beg, end = subtree_ranges[x - 1]
            res = fenwick2.query(0, end) ^ fenwick2.query(0, beg)
            if not beg % 2:
                res ^= fenwick1.query(0, beg)
            if not end % 2:
                res ^= fenwick1.query(0, end)
            print(res)
        else:
            x, y = query[1:]
            beg, end = subtree_ranges[x - 1]
            fenwick1.update(beg, y)
            fenwick1.update(end, y)
            if not beg % 2:
                fenwick2.update(beg, y)
            if not end % 2:
                fenwick2.update(end, y)


if __name__ == '__main__':
    main()

• Dependency
  • teflib.fenwicktree.XorFenwickTree
  • teflib.tgraph.dfs