HZAU 1201 Friends（树形DP）

【题目链接】 http://acm.hzau.edu.cn/problem.php?id=1201

【题目大意】

　　给出一棵树，问每个节点距离六个点以内的点有几个

【题解】

　　定根维护树形DP，Dw[x][i]数组表示从上往下到达的距离为i的点的个数，
　　有Dw[x][i]=sum(Dw[son][i-1])，Up[x][i]表示从下往上距离为i的点的个数，
　　有Up[x][i]=Up[fx][i-1]+Dw[fx][i-1]-Dw[x][i>=2?i-2:0]，
　　两边dfs计算出这两个值，就可以得到每个点的答案了。

【代码】

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

const int N=100010;

vector<int> v[N];

int Dw[N][10],Up[N][10];

void dfs(int x,int fx){

    Dw[x][0]=1;

    for(int i=0;i<v[x].size();i++)if(v[x][i]!=fx){

        dfs(v[x][i],x);

        for(int j=1;j<=6;j++)Dw[x][j]+=Dw[v[x][i]][j-1];

    }

}

void dfs2(int x,int fx){

    Up[x][0]=1;

    if(x!=fx){for(int i=1;i<=6;i++)Up[x][i]=Up[fx][i-1]+Dw[fx][i-1]-Dw[x][i>=2?i-2:0];}

    for(int i=0;i<v[x].size();i++)if(v[x][i]!=fx){dfs2(v[x][i],x);}

}

int T,n;

int main(){

    scanf("%d",&T);

    for(int cas=1;cas<=T;cas++){

        printf("Case #%d:\n",cas);

        scanf("%d",&n);

        for(int i=1;i<=n;i++)v[i].clear();

        memset(Dw,0,sizeof(Dw));

        memset(Up,0,sizeof(Up));

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

            int x,y;

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

            v[x].push_back(y);

            v[y].push_back(x);

        }dfs(1,1); dfs2(1,1);

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

            int res=0;

            for(int j=1;j<=6;j++)res=res+Up[i][j]+Dw[i][j];

            printf("%d\n",res);

        }

    }return 0;

}