전송문 신선제.간단한 판본은 만들기 쉽고 방법도 많다.강화판\(n\leq 10^5\) 은 이전\(O (n ^2)\) 의 방법과 시간, 공간의 복잡도를 감당할 수 없는 것이 분명하다.유지 보수를 고려하여 깊이와 관련된\(dp\): 4
\(f[i][j]\)는\(i\)를 루트 노드로 하는 서브트리의 깊이\(j\) 점이 몇 개인지 나타냅니다
분명히 이것은 유지 보수가 잘 되어 있습니다. (\displaystyle f[i] [j]=\sum {k} f[k] [j-1]\) 를 옮기면 우리는 긴 체인으로 나누어 가속할 수 있습니다.점\(3\)을 일일이 열거해야 하기 때문에 다른 두 점의 정보를 관리할 점\(dp\)가 필요합니다. 4
\(g[i][j]\)는\(i\)를 루트 노드로 하는 서브트리에 점대\(x, y)\)의 개수가 얼마나 되는지 표시하며, 점대\(x, y, xot={y}\)에서\(lca\)까지의 거리는 같고\(lca\)에서\(i\)까지의 거리는\(d-j\)이다.즉, 길이가\(j\)인 체인을 일치시켜야 합니다
전환 방법 고려: 4
분명히 아들로부터 직접 옮길 수 있다. 즉\(g[i][j]=g[k][j+1]\)
4
서로 다른 아들 나무 중에서 두 개를 선택한다.\(g[i][j]=f[k 1][j-1]*f[k 2][j-1]\).이 때 두 결점의\(lca\)는\(i\)여야 합니다
첫 번째 이동은 깊이와 관계가 있지만 이전과 약간의 차이가 있기 때문에 여기서 우리는 긴 체인을 분석하여 최적화할 수 있다.두 번째 이동은 직접 매거를 할 수 있는데 여기서 매거의 깊이는 제한을 받는다. 전체 매거 횟수는\(O(긴 체인 길이)\)이다. 그 다음에 답을 어떻게 지켜야 할지 생각해 보자.분명히 최종 답안은 두 가지가 있다. 4
중심점은 특정한 결점이고 이때 답은\(g[i][0]\)이다
4
중심점은 특정한 결점이 아니며 이때 답은\(f[i][j]*g[k][j+1]+f[k][j-1]*g[i][j]\)이다.주로\(2,1),(1,2)\) 두 가지 상황을 고려했는데 사실\(1,1,1)\이런 것도 고려했지만 이미\((2,1)\)에 포함되었다
이상 과정은 가벼운 아들을 일일이 열거하면서 이동&통계 답안을 작성합니다.주의\(g[i][0]\)는 먼저 추가해야 합니다. 그렇지 않으면 통계가 중복될 수 있습니다.자세한 내용은 코드 참조:
