BZOJ3052(树上带修莫队)

树上莫队的基本思路是把树按dfs序分块，然后先按x所在块从小到大排序，再按y所在块从小到大排序，处理询问即可。

这道题带修改，再加一个时间维即可。

设块大小为T，那么时间复杂度为$O(nT+frac{n^3}{T^2})$，当$T=n^frac23$时，时间复杂度最优，为$n^frac53$.

但是实际测试中，取$T=n^frac23*0.5$跑得比较快，还有询问中如果x所在块大于y所在块，就交换x,y，也可以加快速度。

在BZOJ上卡了两波评测机，BZOJ差点崩了..

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N=100005,M=200005;
int n,m,q,B,e,x,y,op,tt,t1,t2,tp,bl[N],st[N],v[N],w[N],a[N],_a[N],vs[N],g[N],f[N][17],hd[N],d[N],nx[M],to[M];
ll aa,a1[N];
struct nd {
    int x,y,t,id;
    bool operator < (const nd &r) const {
        return bl[x]==bl[r.x]?bl[y]==bl[r.y]?t<r.t:bl[y]<bl[r.y]:bl[x]<bl[r.x];
    }
}b[N];
struct nd2 {int x,y,ls;}c[N];
void ad(int x,int y) {to[++e]=y,nx[e]=hd[x],hd[x]=e;}
int rd() {
    int r=0,c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') r=r*10+c-'0',c=getchar();
    return r;
}

void dfs(int x) {
    st[++tp]=x;
    if(tp==B) {tt++; while(tp) bl[st[tp--]]=tt;}
    for(int i=hd[x];i;i=nx[i]) if(!d[to[i]]) d[to[i]]=d[x]+1,f[to[i]][0]=x,dfs(to[i]);
}
int lca(int x,int y) {
    if(d[x]<d[y]) swap(x,y);
    for(int i=16;~i;i--) if(d[f[x][i]]>=d[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=16;~i;i--) if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

void rv(int x) {
    vs[x]^=1;
    if(vs[x]) aa+=(ll)v[a[x]]*w[++g[a[x]]]; else aa-=(ll)v[a[x]]*w[g[a[x]]--];
}
void gai(int x,int y) {if(vs[x]) rv(x),a[x]=y,rv(x); else a[x]=y;}
void rv(int x,int y) {
    while(x^y) {
        if(d[x]<d[y]) swap(x,y);
        rv(x),x=f[x][0];
    }
}

int main() {
    scanf("%d%d%d",&n,&m,&q),B=pow(n,2.0/3)*0.5;
    for(int i=1;i<=m;i++) v[i]=rd();
    for(int i=1;i<=n;i++) w[i]=rd();
    for(int i=1;i<n;i++) x=rd(),y=rd(),ad(x,y),ad(y,x);
    for(int i=1;i<=n;i++) a[i]=rd(),_a[i]=a[i];
    d[1]=1,dfs(1),tt++;
    while(tp) bl[st[tp--]]=tt;
    for(int j=1;j<17;j++)
    for(int i=1;i<=n;i++)
        f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=q;i++) {
        op=rd(),x=rd(),y=rd();
        if(op) {
            if(bl[x]>bl[y]) swap(x,y);
            b[++t1].x=x,b[t1].y=y,b[t1].t=t2,b[t1].id=t1;
        }
        else c[++t2].x=x,c[t2].y=y,c[t2].ls=_a[x],_a[x]=y;
    }
    sort(b+1,b+1+t1),b[0].x=b[0].y=1;
    for(int i=1,t=0,k;i<=t1;i++) {
        while(t<b[i].t) t++,gai(c[t].x,c[t].y);
        while(t>b[i].t) gai(c[t].x,c[t].ls),t--;
        rv(b[i].x,b[i-1].x),rv(b[i].y,b[i-1].y),rv(k=lca(b[i].x,b[i].y)),a1[b[i].id]=aa,rv(k);
    }
    for(int i=1;i<=t1;i++) printf("%lld
",a1[i]);
    return 0;
}