【BZOJ-3052】糖果公园 树上带修莫队算法

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 100010
#define maxm 100010
#define maxq 100010
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,Q,fk,knum,rt[maxn];long long V[maxm],W[maxn],an[maxn],C[maxn],ans;
struct Edgenode{int to,next;}edge[maxn<<];
int head[maxn],cnt;
void add(int u,int v)
{cnt++;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].to=v;}
void insert(int u,int v)
{add(u,v);add(v,u);}
int stack[maxn],top,dfsx,dfs[maxn],deep[maxn],father[maxn][];
int DFS(int now)
{
int size=;
dfs[now]=++dfsx;
for (int i=; i<=; i++)
if (deep[now]>=(<<i)) father[now][i]=father[father[now][i-]][i-];
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=father[now][])
{
deep[edge[i].to]=deep[now]+;
father[edge[i].to][]=now;
size+=DFS(edge[i].to);
if (size>=fk)
{
knum++;
for (int j=; j<=size; j++) rt[stack[top--]]=knum;
size=;
}
}
stack[++top]=now;
return size+;
}
int LCA(int x,int y)
{
if (deep[x]<deep[y]) swap(x,y);
int dd=deep[x]-deep[y];
for (int i=; i<=; i++)
if (dd&(<<i) && dd>=(<<i)) x=father[x][i];
for (int i=; i>=; i--)
if (father[x][i]!=father[y][i])
x=father[x][i],y=father[y][i];
if (x==y) return x; else return father[x][];
}
bool visit[maxn]; int num[maxn];
void Reverse(int x)
{
if (visit[x]) {visit[x]=; ans-=W[num[C[x]]]*V[C[x]]; num[C[x]]--;}
else {visit[x]=; num[C[x]]++; ans+=W[num[C[x]]]*V[C[x]];}
// printf("%d\n",ans);
}
void Change(int x,int y)
{
if (visit[x]) Reverse(x),C[x]=y,Reverse(x);
else C[x]=y;
}
void work(int x,int y)
{
while (x!=y)
if (deep[x]>deep[y]) Reverse(x),x=father[x][];
else Reverse(y),y=father[y][];
}
struct Asknode
{
int a,b,t,id;
bool operator < (const Asknode & A) const
{
if (rt[a]==rt[A.a] && rt[b]==rt[A.b]) return t<A.t;
else if (rt[a]==rt[A.a]) return rt[b]<rt[A.b];
return rt[a]<rt[A.a];
}
}q[maxq];int numq;
struct Changenode{int a,b,t,p;}ch[maxq];int numc,p[maxq];
int main()
{
n=read(),m=read(),Q=read(); fk=pow(n,2.0/)*0.5;
for (int i=; i<=m; i++) V[i]=read();
for (int i=; i<=n; i++) W[i]=read();
for (int u,v,i=; i<=n-; i++) u=read(),v=read(),insert(u,v);
for (int i=; i<=n; i++) C[i]=read();
for (int i=; i<=n; i++) p[i]=C[i]; DFS();
// puts("OK");
// for (int i=1; i<=n; i++) printf("%d %d %d %d\n",V[i],W[i],dfs[i],p[i]);
// for (int i=1; i<=n; i++) printf("%d ",rt[i]); puts("");
// puts("OK");
while (top) rt[stack[top--]]=knum; for (int i=; i<=Q; i++)
{
int opt=read(),a=read(),b=read();
if (opt) {if (dfs[a]>dfs[b]) swap(a,b); numq++;q[numq].a=a; q[numq].b=b; q[numq].t=numc; q[numq].id=numq;}
else {numc++;ch[numc].a=a;ch[numc].b=b;ch[numc].t=i;ch[numc].p=p[a]; p[a]=b;}
}
sort(q+,q+numq+);
//for (int i=1; i<=numq; i++) printf("%d %d %d %d\n",q[i].a,q[i].b,q[i].id,q[i].t);
for (int i=; i<=q[].t; i++) Change(ch[i].a,ch[i].b);
work(q[].a,q[].b);
int T=LCA(q[].a,q[].b);
Reverse(T); an[q[].id]=ans; Reverse(T);
for (int i=; i<=numq; i++)
{
for(int j=q[i-].t+; j<=q[i].t; j++) Change(ch[j].a,ch[j].b);
for(int j=q[i-].t; j>q[i].t; j--) Change(ch[j].a,ch[j].p);
work(q[i-].a,q[i].a); work(q[i-].b,q[i].b);
T=LCA(q[i].a,q[i].b); Reverse(T); an[q[i].id]=ans; Reverse(T);
}
for (int i=; i<=numq; i++) printf("%lld\n",an[i]);
return ;
}