树剖总结
前言
最近被树剖整得很难受，于是有了这一篇总结。
灵感来源于这几道题：[Ynoi2017] 由乃的 OJ，[SDOI2011] 染色，[TJOI2015] 旅游。
关于树剖
树剖解决的问题一般是动态且与树上的简单路径有关，就是将树上的问题转变到链上，然后用数据结构（线段树）来维护一些复杂信息。
一般解决树剖会遇到的瓶颈：
-
如何处理链上的情况。
-
查询时如何合并剖分开的链。
下文主要记录处理第二个瓶颈的套路。
合并链
这 \(3\) 道题都有一个特点：合并链较难处理，有许多细节。
三个题有异曲同工之处，最后要将起点 \(u\) 跳过的链的答案 \(l\)，和跳完的 \(u'\) 和 \(v'\) 中间的答案 \(mid\)，以及终点跳过链的答案 \(r\) 进行合并。
这三道题最后 \(u'\) 和 \(v'\) 的形态会影响最后的答案，然而 \(u'\) 和 \(v'\) 的形态无非就两种：一种 \(u'\) 在上，一种 \(v'\) 在上。但是有些时候要判一下 \(l\) 和 \(r\) 是否记录过链的答案，否则会对答案产生影响。
以[Ynoi2017] 由乃的 OJ为例，就有：
if(!flagl&&!flagr) memcpy(all,(dep[u]<=dep[v])?now.lans:now.rans,sizeof(all));
else if(id[u]<=id[v]) memcpy(all,(l*(now+r)).lans,sizeof(all));
else memcpy(all,((now+l)*r).lans,sizeof(all));
像旅游和染色就要更复杂一些，应为要判 \(l\) 和 \(r\) 是否记录过链的答案。
小 trick 就是合并时重载运算符，结构体写初始化来简便代码。