https://www.luogu.org/PRoblem/show?pid=3047 我们弄一个f[i][j]表示第i个点向下走j步可以到达的位置的值的和； 这个用dfs就好了； 然后在搞 f[i][j]表示第i点向下走0~j步…. 这个前缀和搞搞那就好了 然后不就好算答案了嘛，容斥一下就好了
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define Ll long longusing namespace std;struct cs{ int to,next;}a[200001];int head[100001],w[100001],fa[100001],f[100001][25];//w[i]表示i节点的值，fa[i]是i的父节点, int m,n,x,y,z,ll;void init(int x,int y){ ll++; a[ll].to=y; a[ll].next=head[x]; head[x]=ll;}void dfs(int x,int y){//当前是x点，其父节点是y fa[x]=y; f[x][0]=w[x]; for(int k=head[x];k;k=a[k].next) if(a[k].to!=y){ dfs(a[k].to,x); for(int j=1;j<=m;j++) f[x][j]+=f[a[k].to][j-1]; } }void cfb(int x){ int ans=0,k=m; ans=f[x][m]; while(x!=1&&k){ ans+=f[fa[x]][--k]; if(k)ans-=f[x][k-1]; x=fa[x]; } printf("%d/n",ans);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n-1;i++)scanf("%d%d",&x,&y),init(x,y),init(y,x); for(int i=1;i<=n;i++)scanf("%d",&w[i]); dfs(1,-1);//1的父节点是-1好了 for(int i=1;i<=n;i++)//dfs时f[i][j]是第i点刚好走j步，现在求前缀和 for(int j=1;j<=m;j++)f[i][j]+=f[i][j-1]; for(int i=1;i<=n;i++)cfb(i);}新闻热点
疑难解答
