乃爱与城市拥挤程度

本文主要是介绍乃爱与城市拥挤程度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

乃爱与城市拥挤程度

题解

本题很明显是一道树形dp，我们可以分别记录下当前节点的和与积。

在i的子树上， $siz_{i}_{j}$ 表示距点i距离为j的点的数量， $mul_{i}_{j}$ 表示距点i为j的点的积，即当前位置当 $k=j$ 时的拥堵值。

$f_{i}$ 为当前点为选定点的人数， $g_{i}$ 为当前点为选定点的拥挤度乘积。

每个点对他的祖先的贡献为 $\frac{mul_{fa_{z},k-z}}{mul_{fa_{z-1},k-z-1}}$ 。我们只需记录下它子孙对其的贡献，与其本身的值即可。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#define MAXN 1000005
using namespace std;
typedef long long LL;
const LL INF=0x3f3f3f3f;
const int mo=1e9+7;
int n,k,father[MAXN];
LL siz[MAXN][15],mul[MAXN][15];
LL dp[MAXN],ct[MAXN],num[15];
int nxt[MAXN],to[MAXN];
int head[MAXN],tot;
#define gc() getchar()
template<typename _T>
inline void read(_T &x)
{_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
void addEdge(int u,int v)
{to[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}
void dfs(int u)
{for(int i=0;i<=k;i++)siz[u][i]=mul[u][i]=1LL;for(int i=head[u];i;i=nxt[i]){int v=to[i];//printf("-->%d %d\n",i,to[i]);     if(v==father[u]) continue;father[v]=u;dfs(v);for(int j=1;j<=k;j++){siz[u][j]+=siz[v][j-1];(mul[u][j]*=(mul[v][j-1]*siz[v][j-1])%mo)%=mo;}}
}
LL qkpow(LL a,LL s)
{LL t=1;while(s){if(s&1)t=(t*a)%mo;a=(a*a)%mo;s>>=1;}return t;
}
void dfs2(int u,int fa)
{  memset(num,0,sizeof(num));LL dep=k,now=u;dp[u]=num[k]=siz[u][k];while(--dep&&father[now]){dp[u]+=siz[father[now]][dep]-siz[now][dep-1];num[dep]=dp[u];now=father[now];}if(father[now]) dp[u]++;dep=k,now=u;ct[u]=mul[u][k]*dp[u]%mo;while(--dep&&father[now]){(ct[u]*=mul[father[now]][dep]*qkpow(mul[now][dep-1]*siz[now][dep-1]%mo,mo-2)%mo)%=mo;(ct[u]*=dp[u]-num[dep+1])%=mo;now=father[now];}for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;dfs2(v,u);}
}
int main()
{ read(n);read(k);for(int i=1;i<n;i++){int u,v;scanf("%d %d",&u,&v);addEdge(u,v);addEdge(v,u);}dfs(1);dfs2(1,0);for(int i=1;i<=n;i++)printf("%lld ",dp[i]);puts("");for(int i=1;i<=n;i++)printf("%lld ",ct[i]);return 0;
}