diqiuyi @ 2023-09-06 13:52:42
rt,过不了样例
#include <bits/stdc++.h>
using namespace std;
int n,m,q,opt,v[100005],dep[100005],tim,f[100005][20],tre,lst[100005],pos[100005],nxt[100005],w[100005],cnt[100005],
a[100005],b[100005],tr[200005],fst[100005],sec[100005],bl[200005],c[100005],block,x,y;
long long now,ans[100005];
vector<int> g[100005];
bitset<100005> vis;
struct qr{
int l,r,id,t,lc;
bool operator <(qr x) const{
return bl[l]^bl[x.l]?l<x.l:r^x.r?r<x.r:t<x.t;
}
}qu[100005];
void dfs(int x,int fa){
fst[x]=++tre,tr[tre]=x,dep[x]=dep[fa]+1,f[x][0]=fa;
for(int i=1;i<=(int)log2(dep[x]);i++)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=0;i<g[x].size();i++)
if(g[x][i]^fa)
dfs(g[x][i],x);
sec[x]=++tre,tr[tre]=x;
}
inline int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=f[x][(int)log2(dep[x]-dep[y])];
if(x==y) return x;
for(int i=(int)log2(dep[x]);~i;i--)
if(f[x][i]^f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void dl(int x){
now-=1ll*w[cnt[c[x]]]*v[c[x]];
cnt[c[x]]--;
}
inline void ad(int x){
cnt[c[x]]++;
now+=1ll*w[cnt[c[x]]]*v[c[x]];
}
inline void Add(int x){
if(vis[tr[x]]){
vis[tr[x]]=0;
dl(tr[x]);
}
else ad(tr[x]),vis[tr[x]]=1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>q,block=pow(n<<1,0.66);
for(int i=1;i<=m;i++) cin>>v[i];
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++)
cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
for(int i=1;i<=n;i++)
cin>>a[i],b[i]=c[i]=a[i];
for(int i=1;i<=q;i++){
cin>>opt;
if(opt) cin>>qu[i-tim].l>>qu[i-tim].r,qu[i-tim].t=tim,qu[i-tim].id=i-tim;
else cin>>x>>y,lst[++tim]=b[x],b[x]=nxt[tim]=y,pos[tim]=x;
}
dfs(1,0);
for(int i=1;i<=q-tim;i++){
if(fst[qu[i].l]>fst[qu[i].r]) swap(qu[i].l,qu[i].r);
if(sec[qu[i].l]>sec[qu[i].r]) qu[i].l=fst[qu[i].l],qu[i].r=fst[qu[i].r],qu[i].lc=-114;
else qu[i].lc=lca(qu[i].l,qu[i].r),qu[i].l=sec[qu[i].l],qu[i].r=fst[qu[i].r];
// if(qu[i].l>qu[i].r) swap(qu[i].l,qu[i].r);
// cout<<qu[i].lc<<'\n';
}
// for(int i=1;i<=n;i++)
// cout<<fst[i]<<' '<<sec[i]<<'\n';
for(int i=1;i<=(n<<1);i++)
bl[i]=(i-1)/block+1;
sort(qu+1,qu+q-tim+1);
for(int i=1,lt=1,rt=0,tt=0;i<=q-tim;i++){
while(lt>qu[i].l) Add(--lt);
while(rt<qu[i].r) Add(++rt);
while(lt<qu[i].l) Add(lt++);
while(rt>qu[i].r) Add(rt--);
while(tt<qu[i].t){
tt++;
c[pos[tt]]=nxt[tt];
// if(lt<=fst[pos[tt]]&&fst[pos[tt]]<=rt) vis[nxt[tt]]=!vis[nxt[tt]],vis[lst[tt]]=!vis[lst[tt]];
// if(lt<=sec[pos[tt]]&&sec[pos[tt]]<=rt) vis[nxt[tt]]=!vis[nxt[tt]],vis[lst[tt]]=!vis[lst[tt]];
if((lt<=fst[pos[tt]]&&fst[pos[tt]]<=rt&&(lt>sec[pos[tt]]||rt<sec[pos[tt]]))
||(lt<=sec[pos[tt]]&&sec[pos[tt]]<=rt&&(lt>fst[pos[tt]]||rt<fst[pos[tt]])))
now-=1ll*v[lst[tt]]*w[cnt[lst[tt]]],cnt[lst[tt]]--,cnt[nxt[tt]]++,now+=1ll*v[nxt[tt]]*w[cnt[nxt[tt]]];
}
while(tt>qu[i].t){
c[pos[tt]]=lst[tt];
// if(lt<=fst[pos[tt]]&&fst[pos[tt]]<=rt) vis[nxt[tt]]=!vis[nxt[tt]],vis[lst[tt]]=!vis[lst[tt]];
// if(lt<=sec[pos[tt]]&&sec[pos[tt]]<=rt) vis[nxt[tt]]=!vis[nxt[tt]],vis[lst[tt]]=!vis[lst[tt]];
if((lt<=fst[pos[tt]]&&fst[pos[tt]]<=rt&&(lt>sec[pos[tt]]||rt<sec[pos[tt]]))
||(lt<=sec[pos[tt]]&&sec[pos[tt]]<=rt&&(lt>fst[pos[tt]]||rt<fst[pos[tt]])))
now-=1ll*v[nxt[tt]]*w[cnt[nxt[tt]]],cnt[nxt[tt]]--,cnt[lst[tt]]++,now+=1ll*v[lst[tt]]*w[cnt[lst[tt]]];
tt--;
}
if(qu[i].lc^-114){
if(vis[qu[i].lc]){
vis[qu[i].lc]=0;
dl(qu[i].lc);
}
else ad(qu[i].lc),vis[qu[i].lc]=1;
}
ans[qu[i].id]=now;
}
for(int i=1;i<=q-tim;i++)
cout<<ans[i]<<'\n';
return 0;
}
/*
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2
*/