@[noip](/space/show?uid=3296)
by _meaningless_ @ 2019-10-01 21:46:50
这道题没有一个log的高效做法吧
by noip @ 2019-10-01 22:07:15
？？？
by pzc2004 @ 2019-10-01 22:12:43
@[WEMS_pzc](/space/show?uid=60075) 是有一个log的做法，但非常不高效
by foreverlasting @ 2019-10-02 13:42:45
@[foreverlastnig](/space/show?uid=32878)
非常不高效还行，大概思路能给蒟蒻说说嘛QAQ
我主要是想看一下复杂度是怎么降下来的
by _meaningless_ @ 2019-10-02 19:30:19
@[zxyoi](/space/show?uid=46382) 先轻重链剖掉，然后对于树上每一个点，将轻边按子树大小降序排序，接着二进制分组，每组是$2^1,2^2,...$条轻边这样子，每一组都用个平衡树维护一下。查询操作利用多树二分的技巧，复杂度降到了一个$log$。修改的时候，重链还是一个$log$的，轻边的话，二进制分组后，分析一下复杂度还是一个$log$的
by foreverlasting @ 2019-10-02 19:58:54