传送门

中文题面就不在阐述 

解题思路：题目上的操作2 对一棵树的一条链进行操作，很容易想到树链剖分。由操作1给的叙述，我们能够想到并查集离线建树。要求一个链上知识点种类的数量，而且 wi 不超过60，利用状压来解决。

///#include<bits/stdc++.h>
///#include<unordered_maps>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>

#define MT(a, b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai = acos(-1.0);
const double E = 2.718281828459;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;

int n, q;
ll value[maxn];
struct node {
    int e;
    int p;
} load[maxn << 1];
int head[maxn], sign;

void add_edge(int s, int e) {
    load[++sign] = node{e, head[s]};
    head[s] = sign;
}

struct node_op {
    int op;
    int x;
    int y;
} op[maxn * 3];

int father[maxn], sizes[maxn], depth[maxn], h_son[maxn];
int top[maxn], id[maxn], ranks[maxn], times;

void dfs1(int s, int pre) {
    sizes[s] = 1;
    depth[s] = depth[pre] + 1;
    for (int i = head[s], e; ~i; i = load[i].p) {
        e = load[i].e;
        if (e ^ pre) {
            father[e] = s;
            dfs1(e, s);
            sizes[s] += sizes[e];
            if (sizes[e] > sizes[h_son[s]])
                h_son[s] = e;
        }
    }
}

void dfs2(int s, int root) {
    top[s] = root;
    id[s] = ++times;
    ranks[times] = s;
    if (!h_son[s])
        return;
    dfs2(h_son[s], root);
    for (int i = head[s], e; ~i; i = load[i].p) {
        e = load[i].e;
        if (e != father[s] && e != h_son[s])
            dfs2(e, e);
    }
}

int p[maxn];

int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}

ll state[maxn << 2];    ///状压数组

void pushup(int sign) {
    state[sign] = state[sign << 1] | state[sign << 1 | 1];
}

void build(int sign, int l, int r) {
    if (l == r) {
        state[sign] = (1 << value[ranks[sign]]);
        return;
    }
    int mid = (l + r) >> 1;
    build(sign << 1, l, mid);
    build(sign << 1 | 1, mid + 1, r);
    pushup(sign);
}

void update(int sign, int l, int r, int s, ll x) {
    if (l == r) {
        state[sign] = 1LL << x; ///注意要用 1LL
        return;
    }
    int mid = (l + r) >> 1;
    if (s <= mid) update(sign << 1, l, mid, s, x);
    else update(sign << 1 | 1, mid + 1, r, s, x);
    pushup(sign);
}

ll query(int sign, int l, int r, int a, int b) {
    if (l == a && r == b) return state[sign];
    int mid = (l + r) >> 1;
    if (b <= mid) return query(sign << 1, l, mid, a, b);
    else if (a > mid) return query(sign << 1 | 1, mid + 1, r, a, b);
    else return query(sign << 1, l, mid, a, mid) | query(sign << 1 | 1, mid + 1, r, mid + 1, b);
}

ll query_line(int a, int b) {
    ll ans = 0;
    while (top[a] != top[b]) {
        if (depth[top[a]] > depth[top[b]])
            swap(a, b);
        ans = ans | query(1, 1, n, id[top[b]], id[b]);
        b = father[top[b]];
    }
    if (depth[a] > depth[b])
        swap(a, b);
    ans = ans | query(1, 1, n, id[a], id[b]);
    return ans;
}

void init() {
    sign = times = 0;
    memset(state, 0, sizeof(state));
    for (int i = 0; i < maxn; i++) {
        h_son[i] = depth[i] = father[i] = sizes[i] = 0;
        top[i] = id[i] = ranks[i] = 0;
        head[i] = -1;
        p[i] = i;
    }
}

int main() {
    init();
    int s, e;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &value[i]);
    }
    for (int i = 1, a, b; i <= q; i++) {
        scanf("%d %d %d", &op[i].op, &op[i].x, &op[i].y);
        if (op[i].op == 1) {
            a = find(op[i].x);
            b = find(op[i].y);
            if (a != b) {
                p[a] = b;
                add_edge(op[i].y, op[i].x);
                add_edge(op[i].x, op[i].y);
            }
        }
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    for (int i = 0; i < maxn; i++) p[i] = i;
    for (int i = 1, a, b; i <= q; i++) {
        if (op[i].op == 1) {
            a = find(op[i].x);
            b = find(op[i].y);
            if (a != b) p[a] = b;
            else continue;
            ll x = value[op[i].x];
            ll y = value[op[i].y];
            ll z = (x + y) / 2;
            update(1, 1, n, id[op[i].x], z);
            update(1, 1, n, id[op[i].y], z);
            value[op[i].x] = value[op[i].y] = z;
        } else {
            if (find(op[i].y) != find(op[i].x))
                printf("-1\n");
            else {
                ll ans = query_line(op[i].x, op[i].y), cnt = 0;
                for (int i = 0; i <= 60; i++) {
                    if (ans >> i & 1) cnt++;
                }
                printf("%d\n", cnt);
            }
        }
    }
}