P4074 [WC2013]糖果公园 (树上带修莫队）
题目链接：P4074 [WC2013]糖果公园
代码
//#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<set> #include<vector> #include<list> #include<queue> #include<cmath> #include<cstring> #include<sstream> #include<cstdio> #include<ctime> #include<map> #include<bitset> #include<stack> #include<string> using namespace std; //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) // char buf[1<<21],*p1=buf,*p2=buf; #define pii pair<int,int> #define pll pair<ll,ll> #define ll long long #define pb push_back #define ull unsigned ll #define rg register #define bug puts("bug"); const long long INF=0x3f3f3f3f3f3f3f3fLL; const int inf = 0x3f3f3f3f; const int maxn = 1e5+10; const int mod = 1e9+7; const double eps = 1e-6; int di[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}}; inline ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*f; } int n,m,k; int V[maxn],W[maxn],C[maxn]; vector<int>ve[maxn]; int siz[maxn],top[maxn],son[maxn],f[maxn]; int deep[maxn]; vector<int>oula(1,0);//欧拉序 int st[maxn],ed[maxn]; ll ans[maxn]; void dfs1(int x,int fa) { st[x]=oula.size(); oula.pb(x); deep[x]=deep[fa]+1; siz[x]=1; f[x]=fa; for(int& y:ve[x]) { if(y!=fa) { dfs1(y,x); siz[x]+=siz[y]; if(siz[y]>siz[son[x]])son[x]=y; } } ed[x]=oula.size(); oula.pb(x); } void dfs2(int x,int t) { top[x]=t; if(son[x])dfs2(son[x],t); for(int &y:ve[x]) { if(y!=son[x]&&y!=f[x])dfs2(y,y); } } int lca(int x,int y) { while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]])swap(x,y); x=f[top[x]]; } return deep[x]>deep[y]?y:x; } int LCA[maxn]; int T; int cntq,cntc; struct node{ int id,l,r,t; void read() { id=cntq; t=cntc; l=rd(); r=rd(); if(st[l]>st[r])swap(l,r); int k=lca(l,r); if(k==l||l==r) { l=st[l]; r=st[r]; } else { l=ed[l]; r=st[r]; LCA[id]=k; } } bool friend operator<(const node& n1,const node& n2) { if(n1.l/T!=n2.l/T)return n1.l<n2.l; if(n1.r/T!=n2.r/T)return n1.r<n2.r; return n1.t<n2.t; } }q[maxn]; struct node1{ int id,p,k; void read() { id=cntc; p=rd(); k=rd(); } }c[maxn]; ll now; int v[maxn]; int cnt[maxn]; void Add(int x,int flag=1) { if(flag)x=C[x]; cnt[x]++; now+=1ll*V[x]*W[cnt[x]]; } void Sub(int x,int flag=1) { if(flag)x=C[x]; now-=1ll*V[x]*W[cnt[x]]; cnt[x]--; } void add(int x) { x=oula[x]; if(v[x])Sub(x); else Add(x); v[x]^=1; } bool in(int x,int i) { return x>=q[i].l&&x<=q[i].r; } void move(int t,int i) { int x=c[t].p; if(in(st[x],i)^in(ed[x],i)) { Sub(C[c[t].p],0); Add(c[t].k,0); } swap(c[t].k,C[c[t].p]); } int main() { n=rd(),m=rd(),k=rd(); for(int i=1;i<=m;i++)V[i]=rd(); for(int i=1;i<=n;i++)W[i]=rd(); for(int i=1;i<n;i++) { int u=rd(),v=rd(); ve[u].pb(v); ve[v].pb(u); } dfs1(1,0); dfs2(1,1); for(int i=1;i<=n;i++)C[i]=rd(); for(int i=1;i<=k;i++) { int op=rd(); if(op==1) { q[++cntq].read(); } else { c[++cntc].read(); } } T=pow(n,2.0/3); sort(q+1,q+1+cntq); int l=1,r=0,t=0; for(int i=1;i<=cntq;i++) { while(l<q[i].l)add(l++); while(l>q[i].l)add(--l); while(r<q[i].r)add(++r); while(r>q[i].r)add(r--); while(t>q[i].t)move(t--,i); while(t<q[i].t)move(++t,i); if(LCA[q[i].id])Add(LCA[q[i].id]); ans[q[i].id]=now; if(LCA[q[i].id])Sub(LCA[q[i].id]); } for(int i=1;i<=cntq;i++)printf("%lld\n",ans[i]); }