[WC 2013] 糖果公园 - sxysxy - 392238

记录编号	392238	评测结果	AAAAAAAAAA
题目名称	[WC 2013] 糖果公园	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	14.479 s
提交时间	2017-04-07 17:21:17	内存使用	11.70 MiB
显示代码纯文本
//锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷烫烫烫
//锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷
//====================================================================================
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdarg>
#include <string>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <list>
#include <queue>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;
  }
  template<typename T>
  inline void splay(T &r){
    char c; bool s = false;
    while((c = readc())){
      if(c >= '0' && c <= '9'){
        r = c^0x30; break;
      }else if(c == '-')s = true;
    }while(isdigit(c = readc()))
      r = r*10+(c^0x30);
    if(s)r = -r;
  }
}using IO::splay;
const int MAXN = 100002;
//===========================树剖以及树分块===========================
struct edge{
  int to, next;
}es[MAXN<<1];
int head[MAXN], _etot;
inline void addedge(int u, int v){
  es[++_etot] = (edge){v, head[u]}; head[u] = _etot;
  es[++_etot] = (edge){u, head[v]}; head[v] = _etot;
}
int size[MAXN], fa[MAXN], son[MAXN], deep[MAXN], top[MAXN];
int dfn[MAXN], dfs_tim;
int stk[MAXN], stktp, bk[MAXN], bsize, bcnt;
void dfs(int u, int f, int d){
  size[u] = 1, fa[u] = f, deep[u] = d, dfn[u] = ++dfs_tim;
  int stkbt = stktp;
  for(int i = head[u]; i; i = es[i].next){
    int to = es[i].to;
    if(to != f){
      dfs(to, u, d+1);
      size[u] += size[to];
      if(size[son[u]] < size[to])son[u] = to;
      if(stktp-stkbt < bsize)continue;
      bcnt++;
      while(stktp > stkbt)bk[stk[stktp--]] = bcnt;
    }
  }
  stk[++stktp] = u;
}
void dfs(int u, int tp){
  top[u] = tp;
  if(!son[u])return;
  dfs(son[u], tp);
  for(int i = head[u]; i; i = es[i].next){ 
    int to = es[i].to;
    if(to != fa[u] && to != son[u])dfs(to, to);
  }
}
int lca(int u, int v){
  int t1 = top[u], t2 = top[v];
  while(t1 != t2){
    if(deep[t1] < deep[t2]){
      swap(u, v); swap(t1, t2);
    }
    u = fa[t1], t1 = top[u];
  }
  return deep[u]<deep[v]?u:v;
}
//============================================================
//==================莫队相关==================================
typedef long long LL;
struct que{
  int u, v, tim;
  LL ans;
  bool operator<(const que &oq)const{
    if(bk[u] == bk[oq.u]){
      if(bk[v] == bk[oq.v])
        return tim < oq.tim;
      else return bk[v] < bk[oq.v]; 
    }else return bk[u] < bk[oq.u]; 
  }
}qs[MAXN];
int rank[MAXN];
bool cmp(int a, int b){return qs[a] < qs[b];};
struct chg{
  int last, pos, val;
}cs[MAXN];
int col[MAXN], cnt[MAXN];
LL w[MAXN], v[MAXN];
bool inans[MAXN];
LL ans = 0;
// modui move
inline void removeC(int u){
  ans -= v[col[u]]*w[cnt[col[u]]--];
  inans[u] = false;
}
inline void insertC(int u){
  ans += v[col[u]]*w[++cnt[col[u]]];
  inans[u] = true;
}
inline void reverse(int u){
  if(inans[u])removeC(u);
  else insertC(u);
}
void insertT(int t){
  if(inans[cs[t].pos]){
    removeC(cs[t].pos);
    col[cs[t].pos] = cs[t].val;
    insertC(cs[t].pos);
  }else col[cs[t].pos] = cs[t].val;
}
void removeT(int t){
  if(inans[cs[t].pos]){
    removeC(cs[t].pos);
    col[cs[t].pos] = cs[t].last;
    insertC(cs[t].pos);
  }else col[cs[t].pos] = cs[t].last;
}
void move(int u, int v){
  while(u != v){
    if(deep[u] > deep[v])reverse(u), u = fa[u];
    else reverse(v), v = fa[v];
  }
}
int last[MAXN];
int cntq = 0, cntg = 0;
void read_data(){
  int n, m, q;
  splay(n); splay(m); splay(q);
  bsize = (int)(ceil(pow(n, 2.0/3.0)));
  for(int i = 1; i <= m; i++)splay(v[i]);
  for(int i = 1; i <= n; i++)splay(w[i]);
  for(int i = 1, x, y; i < n; i++){
    splay(x); splay(y);
    addedge(x, y);
  }
  for(int i = 1; i <= n; i++){
    splay(col[i]); last[i] = col[i];
  }
  dfs(1, 0, 0);
  while(stktp)bk[stk[stktp--]] = bcnt;
  dfs(1, 1);
  for(int i = 1; i <= q; i++){
    int op; splay(op);
    int x, y; splay(x); splay(y);
    if(op){
      if(bk[x] > bk[y])swap(x, y);
      qs[++cntq] = (que){x, y, cntg, 0};
      rank[cntq] = cntq;
    }else{
      cs[++cntg] = (chg){last[x], x, y};
      last[x] = y;
    }
  }
}
void solve(){
  sort(rank+1, rank+1+cntq, cmp);
  int u = 1, v = 1, t = 0;
  for(int i = 1; i <= cntq; i++){
    que &q = qs[rank[i]];
    while(t < q.tim)insertT(++t);
    while(t > q.tim)removeT(t--);
    move(u, q.u); move(v, q.v);
    u = q.u, v = q.v;
    int lcauv = lca(u, v);
    reverse(lcauv); q.ans = ans; reverse(lcauv);
  }
  for(int i = 1; i <= cntq; i++)printf("%lld\n", qs[i].ans);
}
int main(){
  //freopen("test_data.txt", "r", stdin);
  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);
  read_data();
  solve();
  return 0;
}