ett1 ETT 오일러 경로 테크닉, 근데 이제 펜윅을 곁들인 Euler Tour Technique 오일러 경로 테크닉 트리의 한 간선을 양방향 간선(or 반대 방향의 간선 두 개)로 생각한 뒤 루트에서 출발해 루트로 도착하는 그래프(트리)의 오일러 사이클을 찾는 것으로 트리를 표현하는 방식이다. * 오일러 사이클은 시작점=종점인 한붓그리기로 이해하면 됨 이렇게 144125566788997233 255667889972144133 255799887662331441 등... 트리가 주어지고 다음과 같은 쿼리가 주어진다고 하자. 1. i번 노드의 모든 하위 노드(자식, 자식의 자식...)의 값을 w만큼 증가한다. or i번 노드의 모든 상위 노드(부모, 부모의 부모...)의 값을 w만큼 증가한다. 2. i번 노드의 값을 출력한다. DFS로도 가능이야 하지만 트리의 깊이가.. 2021. 8. 5. 이전 1 다음