정점 를 가운데 정점으로 고정하자. 와 인접한 각 방향으로 얼마나 멀리 뻗어 나갈 수 있는지를 생각한다.
어떤 방향으로 뻗어 나갈 수 있는 최대 길이를 그 방향의 길이라고 하자. 정점 를 가운데 정점으로 하는 크기 의 삼각별이 존재하려면, 길이가 이상인 방향이 적어도 개 있어야 한다. 따라서 정점 에서 가능한 가장 큰 삼각별의 크기는 에서의 방향 길이들 중 세 번째로 큰 값이다.
이 값을 모든 정점에 대해 구하면 된다. 트리를 임의로 루트 잡고, 아래 방향 DP와 위 방향 DP를 한다.
를 의 자식 방향으로 내려가서 도달할 수 있는 가장 먼 거리라고 하자. 이는 후위 순회로 구할 수 있다.
그 후 를 에서 부모 방향으로 갔을 때 도달할 수 있는 가장 먼 거리라고 하자. 정점 에서 자식 로 를 넘겨 줄 때는, 에서 방향을 제외한 다른 방향들 중 가장 긴 값을 사용하면 된다.
각 정점에서 자식 방향들의 길이 과, 루트가 아닌 경우 부모 방향의 길이 를 모아 상위 개를 관리한다. 세 번째로 큰 값이 라면, 정점 는 크기 의 삼각별을 각각 하나씩 만든다.
마지막으로 차분 배열을 이용해 모든 에 대해 구간 에 을 더하면 답을 얻을 수 있다.
시간 복잡도는 , 메모리 복잡도는 이다.
