luogu P3047 [USACO12FEB]附近的牛Nearby Cows

树形dp+1

状态好想得不得了：定义f[i][j]为i点在j步以内的所有奶牛数

转移方程的初步形式也很容易得出来：f[i][j]=sum(f[s][j-1])

但是这样会有一个问题，如果j>1，对于每个子结点s，都有继续向下推下去，但这样显然会重复累加一些边。

所以需要减去重复累加的边：f[i][j]=sum(f[s][j])-(f[i][j-2]*(子结点个数-1) （-1是因为要加一次）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
struct EDge
{
    int to,br;
}bian[210005];
int son[100005],len,f[100005][25],sons[100005],n,k;

void add(int a,int b)
{
    bian[++len].to=b;
    bian[len].br=son[a];
    son[a]=len;
    bian[++len].to=a;
    bian[len].br=son[b];
    son[b]=len;
    sons[a]++; 
    sons[b]++;
}

int main()
{
    int i,j,s;
    scanf("%d%d",&n,&k);
    for(i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(i=1;i<=n;i++)
    scanf("%d",&f[i][0]);
    for(j=1;j<=k;j++)
        for(i=1;i<=n;i++)
        {
            for(s=son[i];s;s=bian[s].br)
            f[i][j]+=f[bian[s].to][j-1];
            if(j>1)
            f[i][j]-=(sons[i]-1)*f[i][j-2];
            else 
            f[i][1]+=f[i][0]; 
        }
    for(i=1;i<=n;i++)
    printf("%d
",f[i][k]);
    return 0;
}

luogu P3047 [USACO12FEB]附近的牛Nearby Cows

相关推荐