[일반] LCA HLD로 짰다 이런 저격 맞으면 어케함?

[펜져(penzer27)]

child 넣는 순서보고 저격 할 수 있다 아님?

[익명(61.253)]

HLD를 제대로 이해하고 있지 않음

[익명(61.253)]

가운데 와리가리 존나 긴 경로가 무조건 한 체인으로 엮임. 잘 생각해보셈

[펜져(penzer27)]

child들 보고 제일 처음꺼 그냥 무지성 같은 색갈 줬는데 뭔가 더 있는건가 흠

[익명(112.186)]

나 HLD 공부 안 했지만 이름만으로 유추하면 존나 긴 경로가 Heavy 하나로 묶이고 나머지 정점 하나짜리들이 Light가 되는 거 맞음?

[펜져(penzer27)]

제일 긴 경로부터 주려면 leaf들 depth 보고 정렬해서 루트까지 올라가는 식으로 짜야겠네

[펜져(penzer27)]

depth 큰거부터 차례차례 root나 이미 visit한 노드까지

[펜져(penzer27)]

ㅋㅋ heavy light 내 맘대로 해석하고 있었네

[펜져(penzer27)]

그냥 depth 제일 긴거보는건 LCA용이고 이론적으로는 subtree 개 수 세야 하는구만

[익명(61.253)]

Heavy 라는 이름의 이유지..ㅇㅇ

[익명(49.168)]

체인 하나 바꾸면 서브트리 크기가 2배 이상 되서 logN번 이상 체인이 안 바뀜

[익명(211.224)]

depth 큰 순으로 정렬하면 light edge 최대 루트개고 size 큰 순으로 정렬하면 최대 log N개임

[익명(211.224)]

'depth 제일 긴거보는건 LCA용이고 이론적으로는 subtree 개수 세야 한다' 이건 뭔 말인지 모르겠음