树形DP【洛谷P3047】 [USACO12FEB]附近的牛Nearby Cows

P3047 [USACO12FEB]附近的牛Nearby Cows

先处理出来子树内的。

设\(f(i)(j)\)表示以i为根的子树内距离i为j的答案。

很简单的转移:

\(f(u)(j)=\sum_{f(v)(j-1)}​\)

然后转移出非子树内的，为了解决DP后效性要开一个中间量数组转移一下。

code:

#include <iostream>

#include <cstdio>

#define int long long

using namespace std;

const int wx=100017;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int f[wx][27],g[wx][27];

int head[wx],val[wx];

int n,k,num;

struct e{

	int nxt,to;

}edge[wx*2];

void add(int from,int to){

	edge[++num].nxt=head[from];

	edge[num].to=to;

	head[from]=num;

}

void dfs(int u,int fa){

	f[u][0]=val[u];

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==fa)continue;

		dfs(v,u);

		for(int j=1;j<=k;j++){

			f[u][j]=(f[u][j]+f[v][j-1]);

		}

	}

}

void dp(int u,int fa){

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==fa)continue;

		g[v][1]+=f[u][0];

		for(int j=2;j<=k;j++){

			g[v][j]+=(f[u][j-1]-f[v][j-2]);

		}

		for(int j=1;j<=k;j++)f[v][j]+=g[v][j];

		dp(v,u);

	}

}

signed main(){

//	freopen("a.in","r",stdin);

//	freopen("a.out","w",stdout);

	n=read(); k=read();

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

		int x,y;

		x=read(); y=read();

		add(x,y); add(y,x);

	}

	for(int i=1;i<=n;i++)val[i]=read();

	dfs(1,0); dp(1,0);

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

		for(int j=1;j<=k;j++){

			f[i][j]+=f[i][j-1];

		}

	}

	for(int i=1;i<=n;i++)printf("%lld\n",f[i][k]);

	return 0;

}