삼각별 찾기

정점 $v$를 가운데 정점으로 고정하자. $v$와 인접한 각 방향으로 얼마나 멀리 뻗어 나갈 수 있는지를 생각한다.

어떤 방향으로 뻗어 나갈 수 있는 최대 길이를 그 방향의 길이라고 하자. 정점 $v$를 가운데 정점으로 하는 크기 $K$의 삼각별이 존재하려면, 길이가 $K$ 이상인 방향이 적어도 $3$개 있어야 한다. 따라서 정점 $v$에서 가능한 가장 큰 삼각별의 크기는 $v$에서의 방향 길이들 중 세 번째로 큰 값이다.

이 값을 모든 정점에 대해 구하면 된다. 트리를 임의로 루트 잡고, 아래 방향 DP와 위 방향 DP를 한다.

$down_v$를 $v$의 자식 방향으로 내려가서 도달할 수 있는 가장 먼 거리라고 하자. 이는 후위 순회로 구할 수 있다.

그 후 $up_v$를 $v$에서 부모 방향으로 갔을 때 도달할 수 있는 가장 먼 거리라고 하자. 정점 $v$에서 자식 $u$로 $up_u$를 넘겨 줄 때는, $v$에서 $u$ 방향을 제외한 다른 방향들 중 가장 긴 값을 사용하면 된다.

각 정점에서 자식 방향들의 길이 $down_u+1$과, 루트가 아닌 경우 부모 방향의 길이 $up_v$를 모아 상위 $3$개를 관리한다. 세 번째로 큰 값이 $L_v$라면, 정점 $v$는 크기 $1,2,\ldots,L_v$의 삼각별을 각각 하나씩 만든다.

마지막으로 차분 배열을 이용해 모든 $v$에 대해 구간 $[1,L_v]$에 $1$을 더하면 답을 얻을 수 있다.

시간 복잡도는 $O(N)$, 메모리 복잡도는 $O(N)$이다.