欧拉序树上莫队
通过欧拉序把树上莫队转化成序列莫队。
这里的欧拉序只的是 \(dfs\) 刚遍历到的时候加入点,遍历完整颗子树的时候再加入这个点。设 \(u\) 第一次出现的位置是 \(f[u]\),第二次出现的位置是 \(g[u]\),那么当我要求 \(u\) 到 \(v\) 的信息时,在 \([g[u],f[v]]\) 这段区间中,链上的点除了 \(lca\) 可能不存在,其他点都只会出现一次。而不在链上的点,要么出现零次,要么出现两次。
为什么呢?首先不在 \(lca\) 子树里的点只会出现零次。其次在子树里的但不在链上的点,观察上图,会形成一颗颗子树“挂”在链上。子树有可能在 \(g[u]\) 之前遍历完了,那么都出现零次,有可能在 \(g[u]\) 之后遍历,那么都出现两次。而在链上的点,第一次出现的位置一定在 \(g[u]\) 之前,第二次出现的位置一定在 \(g[u]\) 之后,所以会出现一次。
然后你只要判一下 \(u\) 是否等于 \(lca(u,v)\) 就行了,如果不等于你还要加上 \(lca\) 处的贡献。
P4074 [WC2013] 糖果公园
用欧拉序把树上带修莫队变成序列带修莫队就做完了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
vector<int>e[N];
int n,m,sq,Q,tot,res,a[N],b[N],c[N],p[N],s[N],bl[N],pos[N],cnt[N],vis[N];
int id,d[N],f[N],g[N],ans[N],st[N][25];
struct node{int l,r,t,id;
}q[N];
bool cmp(node x,node y){return bl[x.l]^bl[y.l]?x.l<y.l:bl[x.r]^bl[y.r]?x.r<y.r:x.t<y.t;}
void dfs(int u,int fa)
{f[u]=++id,pos[id]=u,d[u]=d[fa]+1,st[u][0]=fa;for(int v:e[u])if(v!=fa)dfs(v,u);g[u]=++id,pos[id]=u;return;
}
int lca(int x,int y)
{if(d[x]<d[y])swap(x,y);for(int i=20;i>=0;i--)if(d[st[x][i]]>=d[y])x=st[x][i];if(x==y)return x;for(int i=20;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];return st[x][0];
}
void add(int k,int s)
{res-=a[c[k]]*b[cnt[c[k]]];cnt[c[k]]-=(vis[k]*2-1);res+=a[c[k]]*b[cnt[c[k]]];vis[k]=(vis[k]+2+s)%2;return;
}
signed main()
{scanf("%lld%lld%lld",&n,&m,&Q);for(int i=1;i<=m;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++)scanf("%lld",&b[i]),b[i]+=b[i-1];for(int i=1,u,v;i<n;i++)scanf("%lld%lld",&u,&v),e[u].push_back(v),e[v].push_back(u);for(int i=1;i<=n;i++)scanf("%lld",&c[i]);dfs(1,0),sq=pow(id,2.0/3.0);for(int i=1;i<=id;i++)bl[i]=i%sq==1?bl[i-1]+1:bl[i-1];for(int j=1;j<=20;j++)for(int i=1;i<=n;i++)st[i][j]=st[st[i][j-1]][j-1];for(int i=1,op,x,y;i<=Q;i++){scanf("%lld%lld%lld",&op,&x,&y);if(op==0)p[i-tot]=x,s[i-tot]=y;else {if(f[x]>f[y])swap(x,y);q[++tot]={lca(x,y)==x?f[x]:g[x],f[y],i-tot,tot};}}sort(q+1,q+1+tot,cmp);for(int i=1,L=1,R=0,t=0;i<=tot;i++){while(L>q[i].l)add(pos[--L],1);while(R<q[i].r)add(pos[++R],1);while(L<q[i].l)add(pos[L++],-1);while(R>q[i].r)add(pos[R--],-1);while(t<q[i].t){++t;if(L<=f[p[t]]&&f[p[t]]<=R)add(p[t],-1);if(L<=g[p[t]]&&g[p[t]]<=R)add(p[t],-1);swap(c[p[t]],s[t]); if(L<=f[p[t]]&&f[p[t]]<=R)add(p[t],1);if(L<=g[p[t]]&&g[p[t]]<=R)add(p[t],1);}while(t>q[i].t){if(L<=f[p[t]]&&f[p[t]]<=R)add(p[t],-1);if(L<=g[p[t]]&&g[p[t]]<=R)add(p[t],-1);swap(c[p[t]],s[t]);if(L<=f[p[t]]&&f[p[t]]<=R)add(p[t],1);if(L<=g[p[t]]&&g[p[t]]<=R)add(p[t],1);--t;}if(pos[q[i].l]!=lca(pos[q[i].l],pos[q[i].r]))add(lca(pos[q[i].l],pos[q[i].r]),1),ans[q[i].id]=res,add(lca(pos[q[i].l],pos[q[i].r]),-1);else ans[q[i].id]=res;}for(int i=1;i<=tot;i++)printf("%lld\n",ans[i]);return 0;
}