ECNU的oj，题很多的样子。。。orz
附上一篇讲树上差分很不错的blog
初学树上差分第一题吧算是，简单的分析一下就可以发现只需要求出来各条边在query中被覆盖到的次数就可以了。利用边的树上差分很容易就能求出来。每次求出lca之后分为两条链，则cf[u]++,cf[v]++,cf[lca]-=2；即可处理完毕。最后推的时候用dfs从下往上推就可以了。
继续阅读“[LCA][树上差分] ECNU OJ 3631 Delivery Service”
ECNU的oj，题很多的样子。。。orz
附上一篇讲树上差分很不错的blog
初学树上差分第一题吧算是，简单的分析一下就可以发现只需要求出来各条边在query中被覆盖到的次数就可以了。利用边的树上差分很容易就能求出来。每次求出lca之后分为两条链，则cf[u]++,cf[v]++,cf[lca]-=2；即可处理完毕。最后推的时候用dfs从下往上推就可以了。
继续阅读“[LCA][树上差分] ECNU OJ 3631 Delivery Service”