①序列莫队

令BLK=sqrt(n);

按照(l/BLK,r)二元组作为关键字排序，然后暴力转移。

                    ②树上莫队

将树转成dfs序列，设dfn[i]为i点在dfs序列上第一次出现的位置，一个树上的询问(u,v)转化成：

void convert(int u,int v)

{

int l=r=0;

if(dfn[u]<dfn[v])l=dfn[u]+1,r=dfn[v];

if(dfn[v]<dfn[u])l=dfn[v]+1,r=dfn[u];

return (Query)(l,r,lca(u,v));

}

一个点出现两次当没出现过算。

令BLK=sqrt(n);

按照(l/BLK,r)二元组作为关键字排序后处理。

                    ③树上带修改的莫队

另加一维时间轴，在x轴、y轴上跑时顺便在时间轴上跑一下就行了。

令BLK=n^(2/3)

按照(l/BLK,r/BLK,time)三元组作为关键字排序后处理。