树上莫队

块状树的我不会写，这里是括号序列法

类似dfs序，这玩意就是给每个点做个进入和退出的时间戳

dfs序是进入的时间戳，离开并不会使得时间戳增加，但是我们这里给它也记录下时间戳并使其增加，那么我们可以得到长度为 $2n$ 的序列

把树转成一维的括号序列后就可以搞啦

询问点 $x$ 到点 $y$ 的路径？搞出 $[R(x),L(y)]$ 就可以辣（当x为lca时是 $[L(x),L(y)]$）（当然询问区间左右的大小关系是无所谓的）

带修改莫队

把修改的时间戳也记上，排序的时候左右端点块排序，修改时间戳从小到大，暴力还原就行辣

复杂度$O(n^{\frac 53})$

例题：糖果公园

int n, m, Q, v[maxn], w[maxn], c[maxn], last[maxn], cnt[maxn]; ll A[maxn], sum; bool vis[maxn];
int cn, L[maxn], R[maxn], h[17][maxn], dep[maxn], pos[maxc], Bk, B[maxc];
struct node{int l,r,t,id;} q[maxn]; int Q1;
bool cmp(const node &a, const node &b){return B[a.l]<B[b.l] || (B[a.l]==B[b.l] && B[a.r]<B[b.r]) || (B[a.l]==B[b.l] && B[a.r]==B[b.r] && a.t<b.t);}
struct node2{int x,pre,now;} p[maxn]; int Q2;
 
void dfs(int x)
{
    pos[L[x]=++cn]=x;
    rep(o, 1, 16) if (dep[x]>=(1<<o)) h[o][x]=h[o-1][h[o-1][x]]; else break;
    travel(x) if (p->y!=h[0][x]) h[0][p->y]=x, dep[p->y]=dep[x]+1, dfs(p->y);
    pos[R[x]=++cn]=x;
}
 
inline int lca(int x, int y)
{
    if (dep[x]<dep[y]) swap(x,y);
    if (dep[x]!=dep[y])
    {
        int tmp=dep[x]-dep[y];
        rep(o, 0, 16) if (tmp&(1<<o)) x=h[o][x], tmp-=(1<<o); else if (!tmp) break;
    }
    dow(o, 16, 0) if (h[o][x]!=h[o][y]) x=h[o][x], y=h[o][y];
    return x==y?x:h[0][x];
}
inline void Vis(int x)
{
    if (vis[x]) sum-=1LL*v[c[x]]*w[cnt[c[x]]--]; else sum+=1LL*v[c[x]]*w[++cnt[c[x]]];
    vis[x]^=1;
}
inline void change(int x, int col)
{
    if (vis[x]) Vis(x),c[x]=col,Vis(x); else c[x]=col;
}
 
int main()
{
	
    //=================================

    rep(i, 1, n) c[i]=last[i]=read();
     
    dfs(1);
     
	Bk=1750; rep(i, 1, cn) B[i]=(i-1)/Bk+1;
    rep(i, 1, Q)
    {
        int op=read(), x=read(), y=read();
        if (op==1)
        {
            if (L[x]>L[y]) swap(x,y);
            int z=lca(x,y);
            ++Q1, q[Q1]=(node){x==z?L[x]:R[x], L[y], Q2, Q1};
        } else p[++Q2]=(node2){x, last[x], y}, last[x]=y;
    }
    sort(q+1, q+1+Q1, cmp);
    int l=1, r=0, now=0; rep(i, 1, Q1)
    {
        while (now<q[i].t) now++, change(p[now].x, p[now].now);
        while (q[i].t<now) change(p[now].x, p[now].pre), now--;
        while (l<q[i].l) Vis(pos[l++]);
        while (q[i].r<r) Vis(pos[r--]);
        while (q[i].l<l) Vis(pos[--l]);
        while (r<q[i].r) Vis(pos[++r]);
		int x=pos[l], y=pos[r], z=lca(x,y);
        if (x!=z && x!=y) Vis(z);
        A[q[i].id]=sum;
        if (x!=z && x!=y) Vis(z);
    }
	
    //=================================
	
    return 0;
}