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);}新聞熱點
疑難解答
