树上带修莫队
cpp
namespace MoOnTreeDynamic{
// 莫队带修
// 用法：assign(n),加边,init(),添加询问,修改add函数,work()
struct Node{
int id,l,r,t,p;
};
// be块编号，[L,R]块边界，seq括号序，in入序，out出序，dep深度
// par父节点数组，adj邻接表
// top括号序长度，block块大小，tot块数量
vector<int> be,L,R,seq,in,out,dep;
vector<vector<int>> par,adj;
int top,block,tot;
vector<Node> que;// 询问
vector<array<int,2>> c;// 带修辅助数组
vector<int> st;// 状态数组
bool cmp(Node x,Node y){
return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.r]^be[y.r]?be[x.r]<be[y.r]:x.t<y.t));
}
void dfs(int u,int fa){
seq[++top]=u;
in[u]=top;
par[u][0]=fa;
dep[u]=dep[fa]+1;
for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
for(auto v:adj[u]){
if(v==fa)continue;
dfs(v,u);
}
seq[++top]=u;
out[u]=top;
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
while(dep[u]>dep[v])u=par[u][__lg(dep[u]-dep[v])];
if(u==v)return u;
for(int i=__lg(dep[u]);i>=0;i--){
if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
}
return par[u][0];
}
void assign(int n){
seq.assign(2*n+1,0);
in.assign(n+1,0);
out.assign(n+1,0);
dep.assign(n+1,0);
par.assign(n+1,vector<int>(__lg(n)+1,0));
adj.assign(n+1,{});
st.assign(n+1,0);
que.clear();
c={{0,0}};
top=0;
}
void init(){
dfs(1,0);
block=pow(top,2.0/3),tot=(top+block-1)/block;
be.assign(top+1,0);
L.assign(tot+1,0);
R.assign(tot+1,0);
for(int i=1;i<=tot;i++){
L[i]=block*(i-1)+1,R[i]=min(block*i,top);
for(int j=L[i];j<=R[i];j++)be[j]=i;
}
}
void add_update(int x,int y){
c.push_back({x,y});
}
void add_query(int u,int v){
if(in[u]>in[v])swap(u,v);
int p=lca(u,v);
int id=que.size(),t=c.size()-1;
if(p==u)que.push_back({id,in[u],in[v],t,0});
else que.push_back({id,out[u],in[v],t,p});
}
void addEdge(int u,int v){
adj[u].push_back(v);
}
}
using namespace MoOnTreeDynamic;
void solve(){
int n,m,q;
cin>>n>>m>>q;
vector<int> V(m+1),W(n+1),cnt(m+1),C(n+1);
for(int i=1;i<=m;i++)cin>>V[i];
for(int i=1;i<=n;i++)cin>>W[i],W[i]+=W[i-1];
assign(n);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
addEdge(u,v);
addEdge(v,u);
}
init();
for(int i=1;i<=n;i++)cin>>C[i];
for(int i=0;i<q;i++){
int op,x,y;
cin>>op>>x>>y;
if(op==0)add_update(x,y);
else add_query(x,y);
}
auto work=[&](){
sort(que.begin(),que.end(),cmp);
int res=0;
auto add=[&](int x){
st[x]^=1;
res-=W[cnt[C[x]]]*V[C[x]];
if(st[x])cnt[C[x]]++;
else cnt[C[x]]--;
res+=W[cnt[C[x]]]*V[C[x]];
};
auto change=[&](int t){
int pos=c[t][0];
if(st[pos]){
add(pos);
swap(C[pos],c[t][1]);
add(pos);
}
else swap(C[pos],c[t][1]);
};
int l=1,r=0,t=0;
vector<int> ans(que.size());
for(int i=0;i<que.size();i++){
auto [id,ql,qr,qt,p]=que[i];
while(r<qr)add(seq[++r]);
while(r>qr)add(seq[r--]);
while(l<ql)add(seq[l++]);
while(l>ql)add(seq[--l]);
while(t<qt)change(++t);
while(t>qt)change(t--);
if(p)add(p);
ans[id]=res;
if(p)add(p);
}
return ans;
};
for(auto x:work())cout<<x<<"\n";
}