Subtask 1

Với mỗi thao tác loại 1, cập nhật màu mới của đỉnh đó.

Với mỗi thao tác loại 2, thực hiện DFS trên cây con của đỉnh đó để tìm các màu xuất hiện.

Độ phức tạp: ~O(m(n+k))~

Subtask 2

Với mỗi màu, sắp xếp các đỉnh trong màu đó theo thứ tự Euler tour. Giả sử tập các đỉnh có màu i sau khi đã sắp xếp là ~S_i = (a_{i,1},\ a_{i,2},...,\ a_{i,k} )~.

Thực hiện các thao tác sau trên cây:

• Với ~j = 1, 2, ..., k~, tăng trọng số đỉnh ~a_{i,j}~ thêm ~1~ đơn vị

• Với ~j = 1, 2, ..., k-1~, giảm trọng số đỉnh ~lca(a_{i,j}, a_{i,j+1})~ đi ~1~ đơn vị

Khi đó có thể chứng minh rằng: Tổng trọng số trên cây con gốc ~v~ bằng ~1~ nếu trong cây con này có chứa ít nhất 1 đỉnh thuộc ~S_i~, và bằng ~0~ nếu ngược lại.

Thực hiện quy trình tương tự với các màu còn lại, chúng ta có thể giải mỗi truy vấn trong ~O(1)~.

Độ phức tạp ~O(k + nlogn + m)~

Subtask 3/4

Dùng std::set để lưu mỗi tập ~S_i~ theo thứ tự Euler tour, chúng ta có thể thêm hoặc xóa 1 đỉnh bất kỳ, cũng như tìm 2 đỉnh liền kề với đỉnh đó trong ~O(logn)~. Cùng với segment tree để thực hiện truy vấn tìm tổng 1 đoạn theo thứ tự Euler tour, mỗi query có thể xử lý trong ~O(logn)~.

Độ phức tạp: ~O(mlogn)~

#ifndef CPL_TEMPLATE
#define CPL_TEMPLATE
/*
    Normie's Template v2.6
    Changes:
    Added range
*/
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;

// ordered_set library.
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>

// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;

//Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

//File I/O.
#define FILE_IN "9"
#define FILE_OUT "9.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)

//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
#define endl "\n"

//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))

//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
// template<typename T>
// __attribute__((always_inline)) void chkmin(T& a, const T& b) {
//     a=(a<b)?a:b;
// }

// template<typename T>
// __attribute__((always_inline)) void chkmax(T& a, const T& b) {
//     a=(a>b)?a:b;
// }

//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;

//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>

//Custom begin/end shorthand.
#define rnge(rnge) rnge.begin(),rnge.end()

//Quick power of 2.
#define pow2(x) (ll(1)<<x)

//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)

//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
    if (!x) return 1;
    ll res=BOW(a,x/2,p);
    res*=res;
    res%=p;
    if (x%2) res*=a;
    return res%p;
}
ll INV(ll a, ll p)
{
    return BOW(a,p-2,p);
}
//---------END-------//
#endif
int sus(int x) {
    return x*x;
}
struct seg
{
    int val[1200001];
    int def=0;
    int x, tl, tr;
    int t; 
    void reset(int c, int l, int r)
    {

        val[c]=0;
        if (l<r)
        {
            int mid=(l+r)/2;
            reset((c<<1),l,mid);
            reset((c<<1)+1,mid+1,r);
        }
    }
    void upd(int c, int l, int r)
    {
        if (tl>tr) return;
        if (r < tl || tr < l) {
            // sus(1);
            return;
        }
        else if (l>=tl && r <= tr) {
            val[c]+=x;
        }
        else {
            int mid = (l+r)/2;
            if (mid>=tl) upd((c<<1),l,mid);
            if (mid+1<=tr) upd((c<<1)|1,mid+1,r);
        }
    }
    int get(int c, int l, int r)
    {
        if (l<=t && t<=r) {
            if (l==r) return val[c];
            else {
                int mid=(l+r)/2;
                int a = get((c<<1),l,mid);
                int b = get((c<<1)|1,mid+1,r);
                return val[c]+a+b;
            }
        }
        else {
            return 0;
        }
    }
};
seg stl, str;

vector<int> gt[500001];
int n,m,i,j,k,t,t1,u,v,a,b;
int dl[500001],dr[500001],ldd[500001];
int par[500001][20];
int col[500001];

set<int> buc[500001];

void dfs(int x) {
    for (int i = 1; i < 20; i ++) {
        par[x][i] = par[par[x][i-1]][i-1];
    }
    a++; dl[x]=a; ldd[a]=x;
    for (auto g : gt[x]) if (g != par[x][0]) {par[g][0] = x; dfs(g);}
    dr[x]=a;
}

int lca(int u, int v) {
    if (dl[u]<=dl[v] && dr[u]>=dl[v]) return u;
    int x = u;
    for (int i = 19; i >= 0; i--) {
        if (!(dl[par[x][i]]<=dl[v] && dr[par[x][i]]>=dl[v])) x = par[x][i];
    }
    return par[x][0];
}

void pAdd(int x, int v) {
    // cout<<"pAdd "<<x<<' '<<v<<endl;
    stl.x = v; str.x = -v;
    stl.tl = 1; str.tl = 1;
    stl.tr = dl[x]; str.tr = dl[x]-1;
    stl.upd(1, 1, n);
    str.upd(1, 1, n);
} 


void pAdd2(int x, int px, int v) {
    // cout<<"pAdd "<<x<<' '<<v<<endl;
    stl.x = v; str.x = -v;
    stl.tl = dl[px]+1; str.tl = dl[px];
    stl.tr = dl[x]; str.tr = dl[x]-1;
    stl.upd(1, 1, n);
    str.upd(1, 1, n);
} 

int query(int x) {
    stl.t = dl[x]; str.t = dr[x];
    return stl.get(1, 1, n) + str.get(1, 1, n);
}

void cAdd(int x, int c) {
    if (!buc[c].size()) {
        buc[c].insert(dl[x]);
        pAdd(x, 1);
    }
    else {
        buc[c].insert(dl[x]);
        int nl, nr;
        auto it = buc[c].lower_bound(dl[x]);
        if (it != buc[c].begin()) {
            it--;
            nl = ldd[(*it)];
            it++;
        }
        else {
            nl = 1;
        }
        it++;
        if (it != buc[c].end()) {
            nr = ldd[(*it)];
        }
        else {
            nr = 1;
        }
        it--;
        nl = lca(nl, x);
        nr = lca(nr, x);
        if (dl[nr] <= dl[nl] && dl[nl] <= dr[nr]) pAdd2(x, nl, 1);
        else pAdd2(x, nr, 1);
    }
}



void cDel(int x, int c) {
    if (buc[c].size() == 1) {
        buc[c].erase(dl[x]);
        pAdd(x, -1);
    }
    else {
        int nl, nr;
        auto it = buc[c].lower_bound(dl[x]);
        if (it != buc[c].begin()) {
            it--;
            nl = ldd[(*it)];
            it++;
        }

        else {
            nl = 1;
        }
        it++;
        if (it != buc[c].end()) {
            nr = ldd[(*it)];
        }
        else {
            nr = 1;
        }
        it--;
        nl = lca(nl, x);
        nr = lca(nr, x);
        if (dl[nr] <= dl[nl] && dl[nl] <= dr[nr]) pAdd2(x, nl, -1);
        else pAdd2(x, nr, -1);
        buc[c].erase(it);
    }
}

int main()
{
    fio;
    cin>>n>>k>>m;
    for (i=1;i<=n;i++) cin>>col[i];
    for (i=1;i<n;i++) {
        cin>>a>>b;
        gt[a].push_back(b);
        gt[b].push_back(a);
    }
    par[1][0] = 1;
    a=0;
    dfs(1);

    stl.reset(1,1,n);
    str.reset(1,1,n);
    for (i=1;i<=n;i++) cAdd(i, col[i]);

    for (i=1;i<=m;i++) {
        cin>>t;
        if (t==1) {
            cin>>a>>b;
            cDel(a, col[a]);
            col[a] = b;
            cAdd(a, col[a]);
        }
        else {
            cin>>a;
            cout<<query(a)<<endl;
        }
    }
}
// a;