Sample Input

  1 #include<cstdio>  2 #include<algorithm>  3 #include<cmath>  4 //using namespace std;  5 const int maxn = 100005;  6 typedef long long ll;  7 ll ans,res[100005];  8 int n,m,q;  9 ll V[maxn],W[maxn],C[maxn]; 10 int h[maxn],nx[maxn<<1],to[maxn<<1],cnt; 11 int fa[maxn],dep[maxn],sz[maxn],ch[maxn],top[maxn],num[maxn]; 12 int dfn[maxn],stack[maxn],stack_top,dfs_clock; 13 int pos[maxn],pos_count,block_size,block_count,pre[maxn]; 14 bool vis[maxn]; 15 struct TAG1{ 16     int x,y,t,id; 17 }b[maxn]; 18 struct TAG2{ 19     int x,y,t,pre; 20 }c[maxn]; 21 int read(){ 22     int rt=0,fl=1;char ch=getchar(); 23     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)fl=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){rt=rt*10+ch-‘0‘;ch=getchar();} 25     return rt*fl; 26 } 27 bool operator < (TAG1 a,TAG1 b){ 28     if(pos[a.x]==pos[b.x]&&pos[a.y]==pos[b.y])return a.t<b.t; 29     else if(pos[a.x]==pos[b.x])return pos[a.y]<pos[b.y]; 30     else return pos[a.x]<pos[b.x]; 31 } 32 void add_edge(int u,int v){ 33     to[++cnt]=v;nx[cnt]=h[u];h[u]=cnt; 34     to[++cnt]=u;nx[cnt]=h[v];h[v]=cnt; 35 } 36 void dfs1(int x,int pr){ 37     fa[x]=pr;dep[x]=dep[pr]+1;sz[x]=1; 38     for(int i=h[x];i;i=nx[i]){ 39         if(to[i]==pr)continue; 40         dfs1(to[i],x); 41         sz[x]+=sz[to[i]]; 42         if(sz[ch[x]]<sz[to[i]])ch[x]=to[i]; 43     } 44 } 45 void dfs2(int x,int tp){ 46     top[x]=tp; 47     if(ch[x])dfs2(ch[x],tp); 48     for(int i=h[x];i;i=nx[i]){ 49         if(to[i]==ch[x]||to[i]==fa[x])continue; 50         dfs2(to[i],to[i]); 51     } 52 } 53 void dfs3(int x,int pr){ 54     dfn[x]=++dfs_clock; 55     int now=stack_top; 56     for(int i=h[x];i;i=nx[i]){ 57         if(to[i]==pr)continue; 58         dfs3(to[i],x); 59         if(stack_top-now>=block_size){ 60             block_count++; 61             while(now!=stack_top){ 62                 pos[stack[stack_top--]]=block_count; 63             }    64         } 65     } 66     stack[++stack_top]=x; 67 } 68 int lca(int u,int v){ 69     while(top[u]!=top[v])dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]]; 70     return dep[u]<dep[v]?u:v; 71 } 72 void reverse(int x){ 73     if(vis[x])ans-=W[num[C[x]]]*V[C[x]],num[C[x]]--; 74     else num[C[x]]++,ans+=W[num[C[x]]]*V[C[x]]; 75     vis[x]^=1; 76 } 77 void change(int x,int y){ 78     if(vis[x]){reverse(x);C[x]=y;reverse(x);} 79     else C[x]=y; 80 } 81 void solve(int x,int y){ 82     while(x!=y) { 83         if(dep[x]>dep[y])reverse(x),x=fa[x]; 84         else reverse(y),y=fa[y]; 85     } 86 } 87 int main(){ 88     n=read();m=read();q=read(); 89     block_size = pow(n,2.0/3)*0.5; 90     for(int i=1;i<=m;i++)V[i]=read(); 91     for(int i=1;i<=n;i++)W[i]=read(); 92     for(int i=1;i<n;i++)add_edge(read(),read()); 93     for(int i=1;i<=n;i++)pre[i]=C[i]=read(); 94     dfs1(1,0);dfs2(1,1);dfs3(1,0); 95     block_count++; 96     while(stack_top)pos[stack[stack_top--]]=block_count; 97 //  for(int i=1;i<=n;i++)printf("%d ",pos[i]); 98 //  puts("\nfsdfsdds\n"); 99     int c1=0,c2=0;100     for(int i=1;i<=q;i++)101     {102         int typ=read(),x=read(),y=read();103         if(!typ)104         {105             c1++;106             c[c1].x=x;c[c1].y=y;c[c1].pre=pre[x];pre[x]=y;107         }108         else109         {110             c2++;111             if(dfn[x]>dfn[y])std::swap(x,y);112             b[c2].x=x;b[c2].y=y;b[c2].id=c2;b[c2].t=c1;113         }114     }115     std::sort(b+1,b+c2+1);116     for(int i=1;i<=b[1].t;i++)117         change(c[i].x,c[i].y);118     solve(b[1].x,b[1].y);119     int t=lca(b[1].x,b[1].y);120     reverse(t);res[b[1].id]=ans;reverse(t);121     for(int i=2;i<=c2;i++)122     {123         for(int j=b[i-1].t+1;j<=b[i].t;j++)124             change(c[j].x,c[j].y);125         for(int j=b[i-1].t;j>b[i].t;j--)126             change(c[j].x,c[j].pre);127         solve(b[i-1].x,b[i].x);128         solve(b[i-1].y,b[i].y);129         int t=lca(b[i].x,b[i].y);130         reverse(t);res[b[i].id]=ans;reverse(t);131     }132     for(int i=1;i<=c2;i++)133         printf("%lld\n",res[i]);134     return 0;135 }136