Atcoder abc351
https://atcoder.jp/contests/abc351
G - Hash on Tree
给定n点树有根数
值数组a[n]
f(u) = a[u] , 如果u是叶子
f(u) = a[u] + prod f(child of u)如果u非叶子
q次操作,每次 修改 a[pos]=val
,每次修改后输出 f(1)
n,q 2e5
4s
1024mb
我的思路
首先这个是收到深度控制的,如果暴力的更新的话
那么一个想法是能否flat掉这个行为
[a,b,c]x[x,y,1] = [0,a*1+b*y,1]
leaf = [0,ai,1]
非叶子 = [ai,1,0]
然而没找到 矩阵方法或者满足“结合率”的东西
如果能有 矩阵或者结合律满足,就是个线段树维护,就好了
其中 上面的乘还可以拆成左右的包裹,总之如果有办法就好了
但是在尝试中发现要得到 a1+by 这种总是伴随秩的下降,没啥办法
第二个想的是上生成方程, 也没有弄出东西
那么最后就是 能否树的结构通过 轻重链 来完成快速计算(q log n)? 也没想到具体维护方法