1 /**************************************************************  2     Problem: 3052  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:69886 ms  7     Memory:29368 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13   14 using namespace std; 15 typedef long long ll; 16 typedef double lf; 17 const int N = 100005; 18 const int Maxlen = N * 60; 19   20 ll now, ans[N]; 21 int n, m, Qu; 22 int cnt_block, sz_block; 23 ll v[N], w[N], pre[N]; 24 int cnt_c[N]; 25 int q[N], top_q; 26   27 char buf[Maxlen], *c = buf; 28 int Len; 29   30 struct tree_node { 31     int sz, dep, dfn, w; 32     int fa[17]; 33     ll c; 34     bool vis; 35 } tr[N]; 36   37 int cnt_tree; 38   39 struct edge { 40     int next, to; 41     edge() {} 42     edge(int _n, int _t) : next(_n), to(_t) {} 43 } e[N << 1]; 44   45 int first[N], cnt_edge; 46   47 struct oper_query { 48     int x, y, id, t; 49     oper_query() {} 50     oper_query(int _x, int _y, int _i, int _t) : x(_x), y(_y), id(_i), t(_t) {} 51       52     inline bool operator < (const oper_query &X) const { 53         return tr[x].w != tr[X.x].w ? tr[x].w < tr[X.x].w : 54             tr[y].w != tr[X.y].w ? tr[y].w < tr[X.y].w : t < X.t; 55     } 56 } oq[N]; 57   58 int cnt_query; 59   60 struct oper_change { 61     int x, y, pre; 62     oper_change() {} 63     oper_change(int _x, int _y, int _p) : x(_x), y(_y), pre(_p) {} 64 } oc[N]; 65   66 int cnt_change; 67   68 inline int read() { 69     int x = 0; 70     while (*c < ‘0‘ || ‘9‘ < *c) ++c; 71     while (‘0‘ <= *c && *c <= ‘9‘) 72         x = x * 10 + *c - ‘0‘, ++c; 73     return x; 74 } 75   76 inline void Add_Edges(int x, int y) { 77     e[++cnt_edge] = edge(first[x], y), first[x] = cnt_edge; 78     e[++cnt_edge] = edge(first[y], x), first[y] = cnt_edge; 79 } 80   81 void dfs(int p) { 82     int i, x, y; 83     tr[p].dfn = ++cnt_tree; 84     for (i = 1; i <= 16; ++i) 85         tr[p].fa[i] = tr[tr[p].fa[i - 1]].fa[i - 1]; 86     for (x = first[p]; x; x = e[x].next) 87         if ((y = e[x].to) != tr[p].fa[0]) { 88             tr[y].dep = tr[p].dep + 1, tr[y].fa[0] = p; 89             dfs(y); 90             tr[p].sz += tr[y].sz; 91             if (tr[p].sz >= sz_block) { 92                 for (i = 1, ++cnt_block; i <= tr[p].sz; ++i) 93                     tr[q[top_q--]].w = cnt_block; 94                 tr[p].sz = 0; 95             } 96         } 97     q[++top_q] = p; 98     ++tr[p].sz; 99 }100  101 inline int lca(int x, int y) {102     int i;103     if (tr[x].dep < tr[y].dep) swap(x, y);104     for (i = 16; ~i; --i)105         if (tr[tr[x].fa[i]].dep >= tr[y].dep)106             x = tr[x].fa[i];107     if (x == y) return x;108     for (i = 16; ~i; --i)109         if (tr[x].fa[i] != tr[y].fa[i])110             x = tr[x].fa[i], y = tr[y].fa[i];111     return tr[x].fa[0];112 }113  114  115 inline void reverse(int p) {116     if (tr[p].vis)117         now -= w[cnt_c[tr[p].c]--] * v[tr[p].c];118     else119         now += w[++cnt_c[tr[p].c]] * v[tr[p].c];120     tr[p].vis ^= 1;121 }122  123 inline void update(int p, int C) {124     if (tr[p].vis) {125         reverse(p);126         tr[p].c = C;127         reverse(p);128     } else tr[p].c = C;129 }130  131 inline void solve(int x, int y) {132     while (x != y) {133         if (tr[x].dep > tr[y].dep)134             reverse(x), x = tr[x].fa[0];135         else reverse(y), y = tr[y].fa[0];136     }137 }138  139 int main() {140     int i, j, LCA, oper, x, y, tot_Q;141     Len = fread(c, 1, Maxlen, stdin);142     buf[Len] = ‘\0‘;143     n = read(), m = read(), tot_Q = read();144     sz_block = (int) pow(n, (lf) 2.0 / 3) / 2;145     for (i = 1; i <= m; ++i)146         v[i] = read();147     for (i = 1; i <= n; ++i)148         w[i] = read();149     for (i = 1; i < n; ++i)150         Add_Edges(read(), read());151     for (i = 1; i <= n; ++i)152         pre[i] = tr[i].c = read();153      154     tr[1].dep = 1;155     dfs(1);156     while (top_q)157         tr[q[top_q--]].w = cnt_block;158      159     for (i = 1; i <= tot_Q; ++i) {160         oper = read(), x = read(), y = read();161         if (!oper)162             oc[++cnt_change] = oper_change(x, y, pre[x]), pre[x] = y;163         else {164             if (tr[x].dfn > tr[y].dfn) swap(x, y);165             oq[++cnt_query] = oper_query(x, y, cnt_query, cnt_change);166         }167     }168      169     sort(oq + 1, oq + cnt_query + 1);170     for (i = 1,     oq[0].t = 0; i <= cnt_query; ++i) {171         for (j = oq[i - 1].t + 1; j <= oq[i].t; ++j)172             update(oc[j].x, oc[j].y);173         for (j = oq[i - 1].t; j > oq[i].t; --j)174             update(oc[j].x, oc[j].pre);175         if (i == 1) solve(oq[i].x, oq[i].y);176         else solve(oq[i - 1].x, oq[i].x), solve(oq[i - 1].y, oq[i].y);177         LCA = lca(oq[i].x, oq[i].y);178         reverse(LCA), ans[oq[i].id] = now, reverse(LCA);179     }180     for (i = 1; i <= cnt_query; ++i)181         printf("%lld\n", ans[i]);182     return 0;183 }