记录编号 | 458004 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [WC 2013] 糖果公园 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 19.154 s | ||
提交时间 | 2017-10-09 21:48:10 | 内存使用 | 12.52 MiB | ||
#include<bits/stdc++.h> #define v e[i].to #define ll long long using namespace std; const int ma=100005; int n,m,Q,fi[ma],tot,w[ma],dfn[ma<<1],cnt[ma],h[ma],c[ma],ans[ma],pos[ma<<1],o1,o2,st[ma],ed[ma],temp[ma]; int siz[ma],top[ma],fa[ma],son[ma],dep[ma]; struct edge{ int to,next; }e[ma<<1]; void edge_add(int x,int y){ e[++tot].to=y; e[tot].next=fi[x]; fi[x]=tot; } struct Ques{ int l,r,tim,id,lc;ll ans; bool operator < (const Ques&o)const{ if(pos[l]!=pos[o.l])return l<o.l; if(pos[r]!=pos[o.r])return r<o.r; return tim<o.tim; } }q[ma]; struct Change{ int id,from,to; }change[ma]; void dfs1(int x){ dfn[++tot]=x;st[x]=tot; for(int i=fi[x];i;i=e[i].next){ if(fa[x]==v)continue; fa[v]=x;dep[v]=dep[x]+1; dfs1(v);siz[x]+=siz[v]; if(siz[v]>siz[son[x]])son[x]=v; }dfn[++tot]=x;ed[x]=tot; } void dfs2(int x,int y){ top[x]=y; if(son[x])dfs2(son[x],y); for(int i=fi[x];i;i=e[i].next){ if(top[v])continue; dfs2(v,v); } } int get_lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; }return dep[x]<dep[y]?x:y; } bool cmp(Ques x,Ques y){ return x.id<y.id; } int read(){ char ch=getchar(); int a=0; while(!(ch<='9'&&ch>='0'))ch=getchar(); while(ch<='9'&&ch>='0'){ a=(a<<1)+(a<<3)+('0'^ch); ch=getchar(); }return a; } int main() { int __size__ = 128<<20; char *__ptr__ = (char *)malloc(__size__)+__size__; __asm__("movl %0, %%esp\n"::"r"(__ptr__)); freopen("park.in","r",stdin);freopen("park.out","w",stdout); n=read(),m=read(),Q=read(); for(int i=1;i<=m;i++)h[i]=read(); for(int i=1;i<=n;i++)w[i]=read(); for(int i=1;i<n;i++){ int x,y;x=read();y=read(); edge_add(x,y);edge_add(y,x); }tot=0; for(int i=1;i<=n;i++)c[i]=read(),temp[i]=c[i],siz[i]=1; dfs1(1);dfs2(1,1); int len=5000; for(int i=1;i<=tot;i++)pos[i]=(i-1)/len+1; for(int i=1;i<=Q;i++){ int t,x,y;t=read();x=read();y=read(); if(t){ if(st[x]>st[y])swap(x,y); int lc=get_lca(x,y);q[++o1].id=o1; if(lc!=x)q[o1].l=ed[x],q[o1].r=st[y],q[o1].tim=o2,q[o1].lc=lc; else q[o1].l=st[x],q[o1].r=st[y],q[o1].tim=o2; } else{ change[++o2].id=x;change[o2].from=temp[x];change[o2].to=y;temp[x]=y; } }sort(q+1,q+o1+1); int l=1,r=0,t=0;ll now=0; for(int i=1;i<=o1;i++){ while(t<q[i].tim){ t++; if(cnt[change[t].id]&1){ ++ans[change[t].to]; now+=(ll)w[ans[change[t].to]]*(ll)h[change[t].to]; now-=(ll)w[ans[change[t].from]]*(ll)h[change[t].from]; ans[change[t].from]--; }c[change[t].id]=change[t].to; } while(t>q[i].tim){ if(cnt[change[t].id]&1){ ++ans[change[t].from]; now+=(ll)w[ans[change[t].from]]*(ll)h[change[t].from]; now-=(ll)w[ans[change[t].to]]*(ll)h[change[t].to]; ans[change[t].to]--; }c[change[t].id]=change[t].from;t--; } while(l<q[i].l){ cnt[dfn[l]]--; if(cnt[dfn[l]]&1)ans[c[dfn[l]]]++,now+=(ll)w[ans[c[dfn[l]]]]*(ll)h[c[dfn[l]]]; else now-=(ll)w[ans[c[dfn[l]]]]*(ll)h[c[dfn[l]]],ans[c[dfn[l]]]--; l++; } while(l>q[i].l){ l--;cnt[dfn[l]]++; if(cnt[dfn[l]]&1)ans[c[dfn[l]]]++,now+=(ll)w[ans[c[dfn[l]]]]*(ll)h[c[dfn[l]]]; else now-=(ll)w[ans[c[dfn[l]]]]*(ll)h[c[dfn[l]]],ans[c[dfn[l]]]--; } while(r<q[i].r){ r++;cnt[dfn[r]]++; if(cnt[dfn[r]]&1)ans[c[dfn[r]]]++,now+=(ll)w[ans[c[dfn[r]]]]*(ll)h[c[dfn[r]]]; else now-=(ll)w[ans[c[dfn[r]]]]*(ll)h[c[dfn[r]]],ans[c[dfn[r]]]--; } while(r>q[i].r){ cnt[dfn[r]]--; if(cnt[dfn[r]]&1)ans[c[dfn[r]]]++,now+=(ll)w[ans[c[dfn[r]]]]*(ll)h[c[dfn[r]]]; else now-=(ll)w[ans[c[dfn[r]]]]*(ll)h[c[dfn[r]]],ans[c[dfn[r]]]--; r--; } q[i].ans=now+(ll)h[c[q[i].lc]]*(ll)w[ans[c[q[i].lc]]+1]; } sort(q+1,q+o1+1,cmp); for(int i=1;i<=o1;i++)printf("%lld\n",q[i].ans); return 0; }