offline query1 BOJ 11813 - GALAKSIJA (disjoint set, tree, 오프라인쿼리) https://www.acmicpc.net/problem/11813 http://blog.naver.com/nywoo19/221436385751 위 블로그 참고했습니다. 가중치있는 트리가 주어진다. 간선을 주어진 순서대로 자를 것. 자르고 난 후 원하는 값을 그때 그때 출력하는 문제. 원하는 값: 전체 경로에서 경로에포함된 모든 간선의 가중치의 xor값이 0인 경우의 수 트리를 자른다 -> 거꾸로 간선을 이어붙이는 편이 훨씬 쉽다. 1. a ^ b == 0 a == b 2. xor(u,v) : xor(1,u) ^ xor(1,v)임을 이용해야 한다. map mp[MAX]에서 mp[u] = {x, cnt} : 대표값이 u인 set에 포함된 v 중 xor(1,v)값이 x인 것의 개수 cnt 간선 (u,v)를 .. 2020. 3. 18. 이전 1 다음