题目描述
传送门
题解
树上带修改莫队：
1、将树分块，然后离线并将修改和询问分开，对于询问的两个点，将dfs序较小的点作为左端点。
2、将询问排序，关键字为：左端点块的编号、右端点块的编号、最近的修改的时间
3、对于两个询问，转移方式是：将两个左端点的树链状态取反，将两个右端点的树链状态取反。注意取反操作都要刨除树链的lca，在查询的时候要先加上lca、然后查询、然后再减去。
然后这题就是道裸题了。。
注意分块n232跑的最快
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
#define N 100005
#define sz 17
int n,m,k,x,y,opt,cc,cq,val[N],w[N],c[N];
int tot,point[N],nxt[N*2],v[N*2];
int b,tr,dfs_clock,h[N],in[N],f[N][sz+3],belong[N],stack[N],top;
struct data{int x,y,r,id,t;LL ans;}ch[N],q[N];
int now,last[N],cnt[N];bool ext[N];
LL ans;
int read()
{
int x=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
void add(int x,int y)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
}
void dfs(int x,int fa)
{
h[x]=h[fa]+1;in[x]=++dfs_clock;
for (int i=1;i<sz;++i) f[x][i]=f[f[x][i-1]][i-1];
int bottom=top;
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
{
f[v[i]][0]=x;
dfs(v[i],x);
if (top-bottom>=b)
{
++tr;
while (top!=bottom)
belong[stack[top--]]=tr;
}
}
stack[++top]=x;
}
int lca(int x,int y)
{
if (h[x]<h[y]) swap(x,y);
int k=h[x]-h[y];
for (int i=0;i<sz;++i)
if ((k>>i)&1) x=f[x][i];
if (x==y) return x;
for (int i=sz-1;i>=0;--i)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int cmp(data a,data b)
{
return belong[a.x]<belong[b.x]||
(belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y])||
(belong[a.x]==belong[b.x]&&belong[a.y]<belong[b.y]&&a.t<b.t);
}
void change(int x,int opt)
{
int y=cnt[x];
if (opt==1) ans+=(LL)val[x]*w[y+1];
else ans-=(LL)val[x]*w[y];
cnt[x]+=opt;
}
void rev(int x)
{
if (ext[x]) change(c[x],-1);
else change(c[x],1);
ext[x]^=1;
}
void modui(int x,int y)
{
while (x!=y)
{
if (h[x]<h[y]) swap(x,y);
rev(x);x=f[x][0];
}
}
int main()
{
n=read();m=read();k=read();
for (int i=1;i<=m;++i) val[i]=read();
for (int i=1;i<=n;++i) w[i]=read();
for (int i=1;i<n;++i)
{
x=read();y=read();
add(x,y),add(y,x);
}
for (int i=1;i<=n;++i) c[i]=read();
b=pow(n,2.0/3.0)*0.5;dfs(1,0);
while (top) belong[stack[top--]]=tr;
for (int i=1;i<=k;++i)
{
opt=read();
if (!opt)
ch[++cc].x=read(),ch[cc].y=read();
else
{
q[++cq].x=read(),q[cq].y=read();
q[cq].t=cc;q[cq].id=cq;q[cq].r=lca(q[cq].x,q[cq].y);
if (in[q[cq].x]>in[q[cq].y]) swap(q[cq].x,q[cq].y);
}
}
sort(q+1,q+cq+1,cmp);
for (int i=1;i<=q[1].t;++i)
{
last[i]=c[ch[i].x];
c[ch[i].x]=ch[i].y;
}now=q[1].t;
modui(q[1].x,q[1].y);
change(c[q[1].r],1);
q[q[1].id].ans=ans;
change(c[q[1].r],-1);
for (int i=2;i<=cq;++i)
{
if (now<q[i].t)
for (int j=now+1;j<=q[i].t;++j)
{
if (ext[ch[j].x])
change(c[ch[j].x],-1),change(ch[j].y,1);
last[j]=c[ch[j].x];
c[ch[j].x]=ch[j].y;
}
else
for (int j=now;j>q[i].t;--j)
{
if (ext[ch[j].x])
change(c[ch[j].x],-1),change(last[j],1);
c[ch[j].x]=last[j];
}
now=q[i].t;
modui(q[i-1].x,q[i].x);
modui(q[i-1].y,q[i].y);
change(c[q[i].r],1);
q[q[i].id].ans=ans;
change(c[q[i].r],-1);
}
for (int i=1;i<=cq;++i)
PRintf("%lld\n",q[i].ans);
}
