qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

문제 링크: www.acmicpc.net/problem/13515 13515번: 트리와 쿼리 6 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 www.acmicpc.net 다음 2가지 쿼리를 처리하는 문제입니다. 1 i. i번 정점의 색을 바꾼다. 2 u. u와 연결된 정점의 개수를 출력한다. (단, 두 정점이 연결되었다는 것은 두 정점을 연결하는 경로상의 모든 정점의 색이 같다는 것을 의미한다.) 이 문제의 정식 풀이는 Tree DP를 heavy-light decomposition으로 최적화하는 것이고, sqrt decomposition을 통해 오프라인 ..

굿바이 boj 2020 대회에 참가하지 못해서 혼자 문제를 풀어보던 중 G번을 접하게 되었습니다. 문제를 보고 풀이가 금방 떠올랐는데 제 풀이가 알려져 있는 풀이들과는 다른 방식이여서 블로그에 올리게 되었습니다. (이 풀이는 정해보다 복잡한 방법이기 때문에 이렇게 푸는건 추천하지 않습니다. 그냥 이렇게도 풀 수 있구나 하고 재미로 봐주세요.) 문제에 대해 간략하게 설명하자면, 쿼리마다 몇개의 점 v_1, v_2, ... , v_k가 들어오는데 가능한 모든 점의 순서쌍 (v_i, v_j)에 대해 lca의 깊이의 합을 계산해서 출력하는 문제입니다. (단, i

안녕하세요. 블로그를 시작하게 된 qwerasdfzxcl(리프)입니다. 최근 ps에 관심이 생기게 되면서 다른 ps 고인물분들처럼 블로그를 만들어봐야겠다는 생각에 블로그를 시작하게 되었습니다. 주로 포스팅할 내용은 boj 문제풀이, codeforces나 Atcoder 대회 후기, KOI, NYPC와 같은 대회 후기 및 풀이 등을 올릴 예정입니다. 백준 문제풀이나 대회 풀이는 인터넷에 많이 있기 때문에 제 블로그에는 인터넷에 풀이가 없거나 저만의 풀이로 푼 문제의 풀이를 올릴 예정입니다. 수정 날짜: 2021/03/17