CF 161D Distance in Tree 树形DP

一棵树，边长都是1，问这棵树有多少点对的距离刚好为k

令tree(i)表示以i为根的子树

dp[i][j][1]:在tree（i）中，经过节点i，长度为j，其中一个端点为i的路径的个数
dp[i][j][0]:在tree(i)中，经过节点i，长度为j，端点不在i的路径的个数

则目标：∑(dp[i][k][0]+dp[i][k][1])
初始化：dp[i][0][1]=1,其余为0

siz[i]:tree(i)中，i与离i最远的点的距离
递推：
dp[i][j][0]+=dp[i][j-l][1]*dp[soni][l-1][1]
dp[i][j][1]=∑dp[soni][j-1][1]

注意：在更新每一个dp[i]时，先更新dp[i][j][0],再更新dp[i][j][1]

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int maxn=+;

 const int maxk=;

 #define LL long long

 inline int max(int a,int b)

 {

     return a>b?a:b;

 }

 inline int min(int a,int b)

 {

     return a<b?a:b;

 }

 LL dp[maxn][maxk][];

 int siz[maxn];

 struct Edge

 {

     int to,next;

 };

 Edge edge[maxn<<];

 int head[maxn];

 int tot;

 int k;

 void init()

 {

     memset(head,-,sizeof head);

     tot=;

     memset(dp,,sizeof dp);

 }

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].next=head[u];

     head[u]=tot++;

 }

 void solve(int ,int );

 void dfs(int ,int );

 int main()

 {

     init();

     int n;

     scanf("%d %d",&n,&k);

     for(int i=;i<n;i++)

     {

         int u,v;

         scanf("%d %d",&u,&v);

         addedge(u,v);

         addedge(v,u);

     }

     solve(n,k);

     return ;

 }

 void solve(int n,int k)

 {

     dfs(,);

     LL ans=;

     for(int i=;i<=n;i++)

     {

         ans+=(dp[i][k][]+dp[i][k][]);

     }

     cout<<ans<<endl;

     return ;

 }

 void dfs(int u,int pre)

 {

     dp[u][][]=;

     siz[u]=;

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==pre)

             continue;

         dfs(v,u);

         for(int l=;l<=siz[v]+;l++)

         {

             for(int j=l+;j<=siz[u]+l;j++)

             {

                 if(j>k)

                     continue;

                 dp[u][j][]+=dp[u][j-l][]*dp[v][l-][];

             }

         }

         for(int j=;j<=siz[v]+;j++)

             dp[u][j][]+=dp[v][j-][];

         siz[u]=max(siz[u],siz[v]+);

         siz[u]=min(siz[u],k);

     }

 }

巴特西

CF 161D Distance in Tree 树形DP

最新文章

热门文章