CodeForces 160D - Distance in Tree 树型DP

题目给了512MB的空间....用dp[k][i]代表以k为起点...往下面走(走直的不打岔)i步能有多少方案....在更新dp[k][i]过程中同时统计答案..

Program:

#include<iostream>

#include<queue>

#include<stack>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<cmath>

#define ll long long

#define oo 1000000007

#define MAXN 50005

using namespace std;

struct node

{

      int x,y,next;

}line[MAXN*2];

int n,K,dp[MAXN][502],_next[MAXN];

bool used[MAXN];

ll ans;

void addline(int x,int y,int m)

{

      line[m].next=_next[x],_next[x]=m;

      line[m].x=x,line[m].y=y;

      return;

}

void dfs(int x)

{

      int i,j,k;

      k=_next[x];

      dp[x][0]=1;

      while (k)

      {

            if (!used[line[k].y])

            {

                    used[line[k].y]=true;

                    dfs(line[k].y);

                    for (i=K;i>=1;i--)  ans+=dp[x][K-i]*dp[line[k].y][i-1];

                    for (i=K;i>=1;i--)  dp[x][i]+=dp[line[k].y][i-1];

            }

            k=line[k].next;

      }

      return;

}

int main()

{

      int i,j;

      while (~scanf("%d%d",&n,&K))

      {

             memset(_next,0,sizeof(_next));

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

             {

                   int x,y;

                   scanf("%d%d",&x,&y);

                   addline(x,y,i*2-1);

                   addline(y,x,i*2);

             }

             memset(used,false,sizeof(used));

             memset(dp,0,sizeof(dp));

             used[1]=true;

             ans=0;

             dfs(1);

             printf("%I64d\n",ans);

      }

      return 0;

}

巴特西

CodeForces 160D - Distance in Tree 树型DP

最新文章

热门文章