【uoj58】 WC2013

http://uoj.ac/problem/58 (题目链接)

　　给定一棵树，每个点有一个颜色，提供两种操作： 

　　　　1.询问两点间路径上的${\sum{v[a[i]]*w[k]}}$，其中${a[i]}$代表这个点的颜色，${k}$表示这个点是这种颜色第${k}$次出现

　　　　2.修改某个点的颜色

　　带修改树上莫队。%%%vfleaking

　　按左端点所在块为第一关键字，右端点所在块为第二关键字，时间为第三关键字，排序。可能会有疑问可不可以以右端点dfs序为第二关键字？这里我们为了突出第三关键字的作用，选择以右端点所在块为第二关键字。每个节点的dfs序都不同，如果以dfs序为第二关键字的话，第三关键字就没用了。当然这样写也不是不行，但时间会略长。 

　　然后进行树上莫队，将询问和修改分开记录每次询问经过修改或逆修改来使时间倒流或前进。 

　　2个月后重新来看自己的程序，纠结了好久为何这样在树上分块就能保证复杂度的问题，自己总结了几点：

　　UPD 2017.1.3：完了完了不会证复杂度了。。。

　　考虑先后2次询问${(u_i,v_i),(u_{i+1},v_{i+1})}$，块的大小为${s}$，询问以及长度为${n}$。我们分几种情况讨论。

　　1.${u_i,u_{i+1};v_i,v_{i+1}}$在同一块

　　块内的询问是无序的，所以块内转移一次最坏是${s}$，有${n}$组询问。那么复杂度是${O(ns)}$。

　　考虑时间：因为块内的时间是有序的，所以这种情况时间的转移就是按顺序扫过去${O(ns)}$

　　2.${u_i,u_{i+1};v_i,v_{i+1}}$不在同一块

　　思考，这样的转移最多${\frac{n}{s}^2}$次，每次最坏${n}$，那么时间复杂度${O(\frac{n^2}{s^2}*n)}$

　　考虑时间：同理，因为每次转移时间的移动可能是${O(n)}$，所以时间转移的复杂度${O(\frac{n^2}{s^2}*n)}$

　　于是我们为了平衡这两个复杂度，使用均值不等式，可以解得这两个复杂度相加的最小值，当${s=n^{\frac{2}{3}}}$时取到。