H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://ac.nowcoder.com/acm/contest/1100/B
D
e
s
c
r
i
p
t
i
o
n
Description
Description
给定一棵大小为
n
n
n的无根数，要求求出每个点距离它不大于
k
k
k的点流向这个点的值，以及这些点流量的乘积
数据范围：
n
≤
1
0
5
,
k
≤
10
n\leq 10^5,k\leq 10
n≤105,k≤10
S
o
l
u
t
i
o
n
Solution
Solution
树形
d
p
dp
dp，因为是无根树，所以我们先钦定一个根，这里假设为1
设
s
i
z
[
i
]
[
k
]
siz[i][k]
siz[i][k]表示以
i
i
i为根的子树中，距离不大于
k
k
k的流向这个点的值，显然可以得到方程
s
i
z
[
i
]
[
k
]
=
∑
j
∈
i
s
o
n
s
i
z
[
j
]
[
k
−
1
]
siz[i][k]=\sum_{j\in i_{son}} siz[j][k-1]
siz[i][k]=∑j∈isonsiz[j][k−1]
同样地，设
m
u
l
[
i
]
[
k
]
mul[i][k]
mul[i][k]表示以
i
i
i为根的子树中，距离不大于
k
k
k的流向这个点的所有点的值的乘积，得到方程
m
u
l
[
i
]
[
k
]
=
∏
j
∈
i
s
o
n
(
m
u
l
[
j
]
[
k
−
1
]
×
s
i
z
[
j
]
[
k
−
1
]
)
mul[i][k]=\prod_{j\in i_{son}}(mul[j][k-1]\times siz[j][k-1])
mul[i][k]=∏j∈ison(mul[j][k−1]×siz[j][k−1])
注意这里我们只算了以它们为根的子树的贡献，但是实际上，在这道题中，它的祖上
k
k
k辈也要算入贡献当中，所以我们考虑处理这个值
s
i
z
siz
siz比较简单，我们往上跳时，计算沿途点的贡献即可
设
f
i
f_i
fi表示以
i
i
i为扩散中心，距离不大于
k
k
k的流向这个点的值，则
f
i
=
∑
j
∈
i
f
a
t
h
e
r
(
s
i
z
[
j
f
a
t
h
e
r
]
[
h
]
−
s
i
z
[
j
]
[
h
−
1
]
)
f_i=\sum_{j\in i_{father}} (siz[j_{father}][h]-siz[j][h-1])
fi=∑j∈ifather(siz[jfather][h]−siz[j][h−1])
h
h
h表示当前向上跳的高度
详细表示：
然后设
g
i
g_i
gi表示以
i
i
i为扩散中心，距离不大于
k
k
k的流向这个点的所有点的值得乘积
则把之前的+改成*，把-改成/（乘法原理）
好像结束了？
不！！！
因为
m
u
l
mul
mul是没有算自己的（你不能提前知道自己的方案，你必须得知上面有多少）
所以，我们提前把
f
f
f每个阶段的值记录下来，再让
m
u
l
mul
mul乘上自己的方案即可
时间复杂度：
O
(
n
k
)
O(nk)
O(nk)
C
o
d
e
Code
Code
#include<cctype>
#include<cstdio>
#define LL long long
#define N 100010
#define mod 1000000007
using namespace std
;int n
,l
[N
],k
,tot
,father
[N
];
struct node
{int next
,to
;}e
[N
<<1];
inline void add(int u
,int v
){e
[++tot
]=(node
){l
[u
],v
};l
[u
]=tot
;return;}
LL f
[N
],g
[N
],siz
[N
][15],mul
[N
][15],crs
[N
];
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline LL
ksm(LL x
,LL y
)
{
LL ans
=1;
for(;y
;y
>>=1,(x
*=x
)%=mod
) if(y
&1) (ans
*=x
)%=mod
;
return ans
;
}
inline void dp(int x
)
{
for(register int i
=0;i
<=k
;i
++) siz
[x
][i
]=mul
[x
][i
]=1;
for(register int i
=l
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(y
==father
[x
]) continue;
father
[y
]=x
;
dp(y
);
for(register int j
=1;j
<=k
;j
++)
siz
[x
][j
]+=siz
[y
][j
-1],(mul
[x
][j
]*=mul
[y
][j
-1]*siz
[y
][j
-1]%mod
)%=mod
;
}
return;
}
inline void dfs(int x
)
{
int now
=x
;f
[x
]=crs
[k
]=siz
[x
][k
];
for(register int i
=k
-1;i
&&father
[now
];i
--,now
=father
[now
])
f
[x
]+=siz
[father
[now
]][i
]-siz
[now
][i
-1],crs
[i
]=f
[x
];
if(father
[now
]) f
[x
]++;
now
=x
;g
[x
]=mul
[x
][k
]*f
[x
]%mod
;
for(register int i
=k
-1;i
&&father
[now
];i
--,now
=father
[now
])
(g
[x
]*=mul
[father
[now
]][i
]*ksm(mul
[now
][i
-1]*siz
[now
][i
-1]%mod
,mod
-2)%mod
)%=mod
,
(g
[x
]*=f
[x
]-crs
[i
+1])%=mod
;
for(register int i
=l
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(y
==father
[x
]) continue;
dfs(y
);
}
return;
}
signed main()
{
n
=read();k
=read();
for(register int i
=1,x
,y
;i
<n
;i
++)
{
x
=read();y
=read();
add(x
,y
),add(y
,x
);
}
dp(1);dfs(1);
for(register int i
=1;i
<=n
;i
++) printf("%lld ",f
[i
]);
putchar(10);
for(register int i
=1;i
<=n
;i
++) printf("%lld ",g
[i
]);
}
