乃爱与城市拥挤程度
题解
本题很明显是一道树形dp，我们可以分别记录下当前节点的和与积。
在i的子树上，表示距点i距离为j的点的数量，表示距点i为j的点的积，即当前位置当时的拥堵值。
为当前点为选定点的人数，为当前点为选定点的拥挤度乘积。
每个点对他的祖先的贡献为。我们只需记录下它子孙对其的贡献，与其本身的值即可。
源码
#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;
}
谢谢！！！
