트리 DP 클래식 문제
3463 단어 dpcodeforces
분석: 딱 보면 트리 DP의 유형입니다.나무DP의 특징은 모든 잎 노드의 정보로 아버지 노드를 업데이트한 다음에 이 아버지 노드를 잎 노드로 삼아 뿌리 노드까지 층층이 귀속시키는 것이다.여기서 쉽게 생각할 수 있는 잎 노드가 아버지의 노드를 갱신하는 방식은 다음과 같다.
dp[i][j]를 노드 i가 뿌리인 모든 하위 트리의 길이가 j인 경로의 줄로 정의합니다.그러면 쉽게 얻을 수 있다.
dp[i][j]= ∑u(u는 i의 모든 하위 노드) dp[u][j-3-1]
이렇게 층층이 귀속 호출하면 하위 노드에서 루트 노드로 갱신할 수 있다.
그러나 견본은 나무의 곱셈 원리에 따라 경로수를 계산하고 갱신하면서 계산해야 한다.계산의 원칙은 이 노드에 한 개의 지점을 추가할 때마다 이 지점과 앞에 이미 가입한 지점의 총화로 조합하여 곱하는 것이다.
Code:
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int M = int(1e5 + 1), INF = 0x3fffffff, mod = 1000000007;
int dp[50009][509], n, k;
long long ans = 0;
vector<int> v[50009];
void dfs(int p, int prev)
{
int u;
dp[p][0] = 1;
for (int i = 0; i < v[p].size(); i++) {
u = v[p][i];
if (u == prev) continue; // ,
dfs(u, p);
for (int i = 0; i < k; i++)
ans += dp[p][i] * dp[u][k - i -1]; // ,
for (int i=0; i<k; i++)
dp[p][i + 1] += dp[u][i]; //
}
return;
}
int main(void)
{
cin >> n >> k;
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(n, -1);
cout << ans << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
