题意：

给一个带点权 $a_i$ 的 $n$ 个点的树，初始根为 $1$ ，支持 $m$ 次（任意1 / 2)：

1. 换根。
2. 查询两个子树的相同点对数（各取一个点权值相同）。

$1 \leq n \leq 10 ^ 5, 1 \leq m \leq 5 \times 10 ^ 5, 1 \leq a_i \leq 10 ^ 9$ 。

题解：

首先查询转化为以 $1$ 为根的树的 dfs 序序列上的区间查询。

考虑以 $1$ 为根的子树及其 dfs 序：

• 现在的根在结点 $x$ 的子树外侧，则当前的子树还是结点 $x$ 的子树，对应当前子树的区间
• $x$ 为当前根，$x$ 的子树为整个树，对应区间 $[1, n]$ 。
• 当前的根在 $x$ 的子树内，则挖去当前根所在的 $x$ 的孩子的子树，考虑的区间变成 $[1, l - 1], [r + 1, n]$ 的形式。

对于同询问涉及多区间，可差分的信息，差分成若干前缀和的和差。

对于同询问两区间相互贡献，可以差分两边，并做笛卡尔积。

笛卡尔积的结果是 $(l_i, r_i, \operatorname{op})$ ，表示 $[1, l_i]$ 和 $[1, r_i]$ 的相互贡献。

推导的过程是这样的：

$$\begin{aligned} &F(l_1, r_1, l_2, r_2) \\ = &F(1, r_1, l_2, r_2) - F(1, l_1 - 1, l_2, r_2)\\ =&F(1, r_1, 1, r_2) - F(1, r_1, 1, l_2 - 1) - F(1, l_1 - 1, 1, r_2) + F(1, l_1 - 1, 1, l_2 - 1) \end{aligned} $$

查询两个前缀区间的贡献，用两个指针表示前缀已加入集合。由于两个指针可以遵循莫队分块排序的规则移动（复杂度同阶于最小曼哈顿距离生成树），所以是 $n \sqrt m + m$ 的。

不基排也能过。但这时候由于大常数（区间有至多 $9m$ 个），瓶颈可能落在 $\mathcal{O}(m \log m)$ 的排序上。

const int maxn = 1e5 + 10;
vector< vector<int> > g;
vector<int> a, da, idfn, siz, dep, h, belong;
int fa[maxn][21];
int top;
void raw_dfs(int cur, int pre) {
    da[++ top] = a[cur]; idfn[cur] = top; dep[cur] = dep[pre] + 1;
    siz[cur] = 1; fa[cur][0] = pre;
    rep(i,1,20) fa[cur][i] = fa[fa[cur][i - 1]][i - 1];
    for(int ver : g[cur]) if(ver != pre) {
            raw_dfs(ver, cur);
            siz[cur] += siz[ver];
        }
}
inline int lowbit(int &x) { return x & (-x); }
inline int jump(int cur, int tm) {
    for(; tm; tm -= lowbit(tm)) cur = fa[cur][h[lowbit(tm)]];
    return cur;
}

struct ask { int l, r, sign, id; };
inline bool mocmp(ask &a, ask &b) {
    return belong[a.l] ^ belong[b.l] ? belong[a.l] < belong[b.l] : belong[a.l] & 1 ? a.r < b.r : a.r > b.r;
}
int cnt[2][maxn], n;
ll calc = 0;
inline void add(int x, int id) {
    ++ cnt[id][da[x]]; calc += cnt[id ^ 1][da[x]];
}
inline void del(int x, int id) {
    -- cnt[id][da[x]]; calc -= cnt[id ^ 1][da[x]];
}

inline void brk(int x, int root, vector< pair<int,int> > &vec) {
    if(x == root) { vec.push_back({n, 1}); return ; }
    int s = root;
    if(dep[x] < dep[root]) s = jump(s, dep[root] - dep[x] - 1);
    if(dep[x] >= dep[root] || fa[s][0] != x) {
        vec.push_back({idfn[x] + siz[x] - 1, 1});
        if(idfn[x] != 1) vec.push_back({idfn[x] - 1, -1});
    } else {
        int l = idfn[s], r = idfn[s] + siz[s] - 1;
        if(r != n) {
            vec.push_back({n, 1});
            vec.push_back({r, -1});
        }
        if(l != 1) vec.push_back({l - 1, 1});
    }
}

signed main() {
    n = read();
    int m = read();
    vector<int> b(n);
    a.resize(n + 1), da.resize(n + 1); g.resize(n + 1); idfn.resize(n + 1); siz.resize(n + 1); dep.resize(n + 1); h.resize(n + 1); belong.resize(n + 1);

    vector<ll> ans(m);
    for(int i = 1; (1 << i) <= n; ++ i)  h[1 << i] = i;
    rep(i,1,n) a[i] = read(), b[i - 1] = a[i];
    sort(b.begin(), b.end());
    auto ed = unique(b.begin(), b.end());
    rep(i,1,n) a[i] = lower_bound(b.begin(), ed, a[i]) - b.begin() + 1;
    int u, v;
    rep(i,1,n - 1) {
        u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    raw_dfs(1, 0);
    vector< ask > as;
    int root = 1, opt, x, y, tot = -1;
    rep(i,1,m) {
        opt = read();
        if(opt == 1) {
            root = read();
        } else {
            x = read(), y = read();
            vector< pair<int,int> > ta, tb;
            brk(x, root, ta); brk(y, root, tb);
            ++ tot;
            for(auto &ita : ta) for(auto &itb : tb) {
                    int a = ita.first, b = itb.first;
                    if(a > b) swap(a, b);
                    as.push_back({a, b, ita.second * itb.second, tot});
                }
        }
    }
    int mbs = max(1, (int)(n / sqrt(as.size() * 2.0 / 3)));
    rep(i,1,n) belong[i] = (i - 1) / mbs + 1;
    sort(as.begin(), as.end(), mocmp);
    int l = 0, r = 0;
    for(ask &cur : as) {
        // expand first
        while(r < cur.r) add(++ r, 1);
        while(l < cur.l) add(++ l, 0);
        while(r > cur.r) del(r --, 1);
        while(l > cur.l) del(l --, 0);
        ans[cur.id] += cur.sign * calc;
    }
    rep(i,0,tot) printf("%lld\n", ans[i]);
    return 0;
}