[일반] f번 lca는 썼어야 되나요?

[익명(116.121)]

아까 어떤 고닉분 말 듣고 생각해봤는데

lca 써서 n*(logn)^2 에 돌아가는게 맞나요??

[대학원오지마세요(publfl)]

그렇게 푼사람도 있고 HLD 쓴사람도 있고. 난 그냥 NlogN으로 품

[익명(116.121)]

nlogn 이 어떤식으로 가능한가요..???

[대학원오지마세요(publfl)]

i번째 답을 구할때 이전까지 구한 답이 ans라고 가정하면, i번째 노드에서 ans번째 위까지의 조상까지만 뒤져보면 됨. 그리고 그렇게 얻은 답을 이용해 ans를 갱신해주고. 이러면 harmonic sum 비슷한 이유로 NlogN만에 구해짐

[익명(116.121)]

와 자세한 설명 정말 감사합니다!! 그러면 이문제를 풀기위해 사전 지식은 HLD, LCA, harmonic sum 정도로 생각하면 될까요?

[대학원오지마세요(publfl)]

그리디, tree DP, DP최적화 정도?

[익명(116.121)]

감사합니다!

[익명(219.250)]

보니까 그냥 트리 위에서 거리 저장하면서 DFS 돌려도 되더라고요 이걸 왜 못 봤지..