F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register |
---|
MainBoard >> http://codeforces.com/contest/1010/problem/F |
save_code @ 2018-07-27 20:48:18
这道题 可以树链剖分+FFT
一个重链上的多项式 可以分解成 所有轻链多项式的卷积 记录这些多项式,他们的度数和不超过N*LG(N) 当一个点从重链变成轻链的时候 合并这些多项式 变成一个然后 添加到他的兄弟节点(肯定是重链节点) 多项式中 当然合并的话用到了分治+FFT 优先选择 SIZE最小的两个多项式合并 这个复杂度貌似也是N*LG(N)^3 |
save_code @ 2018-07-27 21:31:16
好像可以推广到一般的树上
|
nzhtl1477 @ 2018-07-28 13:06:27
这题怕是我一个同学出的原题。。
|
save_code @ 2018-07-28 14:58:41
CF 照搬原题??管它反正卧没有做过
|
nzhtl1477 @ 2018-07-28 17:32:56
orz save_code
|