糖果公园（树上带修莫队）

糖果公园

由于国庆节比赛过多，因此这题断断续续写了好几天。。。

题意：

给定一棵树，每个点的颜色，每种颜色的价值（由遍历次数和颜色种类决定）。然后有一种操作和一种询问：
操作0：修改某个点的颜***r> 询问1：询问 $x, y$ 两点之间总价值（价值定义具体见题意）

思路：树上莫队+带修莫队

（关键词：括号序）树上莫队核心：处理出树的括号序（括号序：在 $d f s$ 过程中进入和离开某个点时都要打上标记），在括号序上进行普通莫队（还是有点不普通）。
（关键词：遍历次数的奇偶）括号序上的莫队算法：关键在于知道什么时候该加入某个点的贡献，什么时候该退出某个点的贡献。考虑在遍历完一整颗子树后，每个节点肯定会被遍历两次，而此处的“两次”正好对应于一次加入贡献，一次退出贡献。因此如果给每个节点一个遍历次数的标记；当其为奇数时，就考虑其贡献；当其为偶数时，就退出其贡献。这样做还有个好处是在带修改时，可以直接通过被修改点的遍历次数的奇偶来判定修改当前点后是否需要重新计算其贡献。
（关键词：LCA是否为路径的端点）同时还需要注意一个细节：当考虑从 $x$ 点沿路径到达 $y$ 点时，如何保证我们想要加入贡献的节点在括号序中都只被遍历了一次？
做法要点：
1. 若 $x$ 点和 $y$ 点在不同的子树上，给当前询问使用“离开”版的 $x$ 序号，“进入”版的 $y$ 序号；
  若 $x$ 或 $y$ 就是 $x, y$ 的 $L C A$ ，给当前询问使用“进入”版的 $x$ 序号，“进入”版的 $y$ 序号。
2. 若 $x$ 点和 $y$ 点在不同的子树上，最终计算贡献时会发现二者的 $L C A$ 并不会被遍历到！因为整个遍历过程中都是在 $L C A$ 的括号中移动的，故统计答案时要额外加上 $L C A$ 的贡献。
然后就真正的是普通的带修莫队啦，最优分块依然是 $\sqrt[3]{i d * t}$ （其中 $i d$ 是括号序的大小； $t$ 是修改操作的数量，也就是时间的范围）（不过好像大家都是玄学分块？或者说我这个是玄学分块QAQ？）
补充： $L C A$ 采用 $s t$ 表求法，询问的排序采用了奇偶化排序。

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, m ,QQ, cnt0, cnt1, len;
int v[maxn], w[maxn], c[maxn], cc[maxn];
int deep[maxn], fa[maxn], st[maxn][20];
int id1[maxn], id2[maxn], rk[maxn*2], id;
int head[maxn], to[maxn*2], nxt[maxn*2], tot;
int vis[maxn], times[maxn];
ll cur, ans[maxn];

inline void add_edge(int u, int v) {
    ++tot; to[tot]=v; nxt[tot]=head[u]; head[u]=tot;
    ++tot; to[tot]=u; nxt[tot]=head[v]; head[v]=tot;
}

struct P{
    int pos, pre, cg;
}p[maxn];

struct Q{
    int l, r, t, id;
    friend bool operator < (const Q &a, const Q &b) {
        if((a.l-1)/len!=(b.l-1)/len) return a.l<b.l;
        if((a.r-1)/len!=(b.r-1)/len) {
            if((a.l-1)/len%2) return a.r>b.r;
            return a.r<b.r;
        }
        if((a.r-1)/len%2) return a.t>b.t;
        return a.t<b.t;
    }
}q[maxn];

void dfs(int u, int f) {
    deep[u]=deep[st[u][0]=fa[u]=f]+1; rk[id1[u]=++id]=u;
    for(int i=head[u]; i; i=nxt[i]) {
        int v=to[i];
        if(v!=f) dfs(v,u);
    }
    rk[id2[u]=++id]=u;
}

int lca(int x, int y) {
    if(deep[x]>deep[y]) swap(x,y);
    for(int i=19; i>=0; --i)
        if(deep[st[y][i]]>=deep[x]) y=st[y][i];
    if(x==y) return x;
    for(int i=19; i>=0; --i)
        if(st[x][i]!=st[y][i]) x=st[x][i], y=st[y][i];
    return fa[x];
}

void add(int u) {
    if(vis[u]) cur-=1ll*w[times[c[u]]--]*v[c[u]];
    else       cur+=1ll*w[++times[c[u]]]*v[c[u]];
    vis[u]^=1;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read(), QQ=read();
    for(int i=1; i<=m; ++i) v[i]=read();
    for(int i=1; i<=n; ++i) w[i]=read();
    for(int i=1; i<n; ++i) add_edge(read(),read());
    for(int i=1; i<=n; ++i) c[i]=cc[i]=read();
    dfs(1,0);
    for(int j=1; j<18; ++j)
        for(int i=1; i<=n; ++i) st[i][j]=st[st[i][j-1]][j-1];
    while(QQ--) {
        int f=read(), x=read(), y=read();
        if(!f) ++cnt0, p[cnt0].pos=x, p[cnt0].pre=cc[x], p[cnt0].cg=cc[x]=y;
        else {
            if(id1[x]>id1[y]) swap(x,y);
            ++cnt1, q[cnt1]=(Q){lca(x,y)==x?id1[x]:id2[x],id1[y],cnt0,cnt1};
        }
    }
    len=pow(1ll*id*max(1,cnt0),1.0/3);
    sort(q+1,q+1+cnt1);
    int l=1, r=0, t=0;
    for(int i=1; i<=cnt1; ++i) {
        while(l<q[i].l) add(rk[l++]);
        while(l>q[i].l) add(rk[--l]);
        while(r<q[i].r) add(rk[++r]);
        while(r>q[i].r) add(rk[r--]);
        while(t<q[i].t) {
            t++;
            if(vis[p[t].pos]) {
                add(p[t].pos);
                c[p[t].pos]=p[t].cg;
                add(p[t].pos);
            }
            else c[p[t].pos]=p[t].cg;
        }
        while(t>q[i].t) {
            if(vis[p[t].pos]) {
                add(p[t].pos);
                c[p[t].pos]=p[t].pre;
                add(p[t].pos);
            }
            else c[p[t].pos]=p[t].pre;
            t--;
        }
        int x=rk[l], y=rk[r], LCA=lca(x,y);
        if(x!=LCA) {
            add(LCA);
            ans[q[i].id]=cur;
            add(LCA);
        }
        else ans[q[i].id]=cur;
    }
    for(int i=1; i<=cnt1; ++i) printf("%lld\n", ans[i]);
}