UVa (12424) Answering Queries on a Tree

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;


#define gc getchar unlocked
#ifndef ONLINE JUDGE
#define gc getchar
#endif // ONLINE JUDGE

#define pc putchar_unlocked
#ifndef ONLINE JUDGE
#define pc putchar
#endif // ONLINE JUDGE

#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define eps             1e-9
#define inf             0x3f3f3f3f
#define INF             2e18
#define LL              long long
#define ULL             unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define rall(a)         a.rbegin(),a.rend()
#define SQR(a)          ((a)*(a))
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define Iterator(a)     __typeof__(a.begin())
#define rIterator(a)    __typeof__(a.rbegin())
#define FOR(a,it)       for(Iterator(a) it = a.begin();it != a.end(); it++)
#define rFOR(a,it)      for(rIterator(a) it = a.rbegin();it != a.rend(); it++)
#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define CasePrint       pc('C'); pc('a'); pc('s'); pc('e'); pc(' '); write(qq++,false); pc(':'); pc(' ')
#define vi              vector <int>
#define vL              vector <LL>
#define For(I,A,B)      for(int I = (A); I  < (B); ++I)
#define rFor(I,A,B)     for(int I = (A); I >= (B); --I)
#define Rep(I,N)        For(I,0,N)
#define REP(I,N)        For(I, 1, N + 1)
#define gti             int, vi, greater<int>
#define gtL             LL, vL, greater<LL>
#define Found(a, b)     a.find(b) != a.end()

const int MOD = 1e9 + 7;
int fx[] = {-1,+0,+1,+0,+1,+1,-1,-1,+0};
int fy[] = {+0,-1,+0,+1,+1,-1,+1,-1,+0};
int day[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//template <typename T> using orderset = tree <T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; // find_by_order, order_of_key
template <typename T> inline bool isLeap(T y) {return (y % 400 == 0) || (y % 100 ? y % 4 == 0 : false); }
template <typename T> inline T GCD (T a,T b ) {a = abs(a);b = abs(b); if(a < b) swap(a, b); while ( b ) { a = a % b; swap ( a, b ); } return a;}
template <typename T> inline T EGCD(T a,T b,T &x,T &y){if(a == 0) {x = 0;y = 1;return b;}T x1, y1;T d = EGCD(b % a, a, x1, y1);x = y1 - (b / a) * x1;y = x1;return d;}
template <typename T> inline T LCM(T x,T y){T tp = GCD(x,y);if( (x / tp) * 1. * y > 9e18) return 9e18;return (x / tp) * y;}
template <typename T> inline T BigMod(T A,T B,T M = MOD){T ret = 1;while(B){if(B & 1) ret = (ret * A) % M;A = (A * A) % M;B = B >> 1;}return ret;}
template <typename T> inline T InvMod (T A,T M = MOD){return BigMod(A,M-2,M);}
//template <typename T> void Compress(T * in, int n){vector <T> vv;for(int i = 0; i < n; i++) vv.pb(in[i]);Unique(vv);for(int i = 0; i < n; i++) in[i] = lower_bound(all(vv), in[i]) - vv.begin();}
//template <typename T> void Compress(vector <T> &in){vector <T> vv;for(T x : in) vv.pb(x);Unique(vv);for(int i = 0; i < in.size(); i++) in[i] = lower_bound(all(vv), in[i]) - vv.begin();}
/*---------------------------fast I/O------------------------------------*/
#define scani2(a,b) scani(a) , scani(b)
#define scani3(a,b,c) scani(a), scani(b), scani(c)
#define scani4(a,b,c,d) scani(a), scani(b), scani(c), scani(d)
#define scani5(a,b,c,d,e) scani(a), scani(b), scani(c), scani(d) , scani(e)
template <typename T> T scani(T &n){n = 0;bool negative = false;char c = gc();while( c < '0' || c > '9'){if(c == '-') negative = true;c = gc();}while(c >= '0' && c <= '9'){n = n*10 + c-48;c = gc();}if(negative) n = ~(n-1);return n;}
template <typename T> void write(T n,int type = true){if(n<0) {pc('-');n = -n;}if(!n) {pc('0');if(type==32) pc(' '); else if(type) pc('\n'); return;}char buff[22];int len = 0;while(n) buff[len++] = n%10+48,n/=10;for(int i=len-1;i>=0;i--) pc(buff[i]);if(type==32) pc(' '); else if(type) pc('\n');}
int scans(char *a){int i=0;char c = 0;while(c < 33) c = gc();while(c > 33){a[i++] = c;c = gc();}a[i] = 0;return i;}
/*********************************************** End of template *********************************************/


#ifdef Sieve
const int pSz = 2000006;
bool np[pSz + 10]; vi prime; int prime_size;void sieve(){np[0] = np[1] = 1;prime.pb(2);for(LL i = 4; i <= pSz; i+=2) np[i] = 1;for(LL i = 3; i <= pSz; i+=2){if(!np[i]){prime.pb(i);for(LL j = i * i; j <= pSz; j += (i << 1)) np[j] = 1;}}prime_size = prime.size();}
#endif

#ifdef Combi
const int nSz = 2000006;
LL F[nSz + 1], tMod = MOD;
void Factorial(){ F[0] = 1; for(int i = 1; i <= nSz; i++) F[i] = (F[i - 1] * i) % tMod; }
inline LL nCr(int n, int r) { return (F[n] * InvMod((F[n - r] * F[r]) % tMod, tMod)) % tMod; }
#endif

#ifdef Z_Algo
void zAlgo(char *s, int *z){
    int L, R, sz; sz = strlen(s); z[0] = L = R = 0;
    For(i, 1, sz) { z[i] = 0; if(i <= R) z[i] = min(z[i - L], R - i + 1); while(i + z[i] < sz && s[i + z[i]] == s[z[i]]) z[i]++; if(i + z[i] - 1 > R) L = i, R = i + z[i] - 1; }
}void zAlgo(string &s, int *z){
    int L, R, sz; sz = s.size(); z[0] = L = R = 0;
    For(i, 1, sz) { z[i] = 0; if(i <= R) z[i] = min(z[i - L], R - i + 1); while(i + z[i] < sz && s[i + z[i]] == s[z[i]]) z[i]++; if(i + z[i] - 1 > R) L = i, R = i + z[i] - 1; }
}void zAlgo(int *s, int *z, int n){
    int L, R, sz; sz = n; z[0] = L = R = 0;
    For(i, 1, sz) { z[i] = 0; if(i <= R) z[i] = min(z[i - L], R - i + 1); while(i + z[i] < sz && s[i + z[i]] == s[z[i]]) z[i]++; if(i + z[i] - 1 > R) L = i, R = i + z[i] - 1; }
}
#endif // Z_Algo


/********************************************* define Template *************************************************/

template <typename T> inline T SqrDis(T x1, T y1, T x2, T y2){return SQR(x1 - x2) + SQR(y1 - y2);}
template <typename T> inline T Area2(T Ax, T Ay, T Bx, T By, T Cx, T Cy){T ret = Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By);
    if(ret < 0) return ret = -ret;
    return ret;
}
/**************************************************** GEO ******************************************************/
const int N = 200005;
const int M = 44444;
const ULL hs = 3797;

struct data{
    int cnt[11];
    data() {
        memset(cnt, 0, sizeof(cnt));
    }
};

int chainNo, limit, chainId[N], chainHead[N], posInBase[N], baseArray[N];
int Level[N], LCA[N][22], subSize[N];
data Tree[N << 2];
int n, in[N];
vi G[N];


void Clear()
{
    For(i, 1, n + 1) G[i].clear();
    memset(chainHead, -1, sizeof(chainHead));
    memset(LCA, 0, sizeof(LCA));
    memset(Tree, 0, sizeof(Tree));
}


void DFS(int x, int lv, int F)
{
    LCA[x][0] = F;
    Level[x] = lv;
    subSize[x] = 1;
    Rep(i, G[x].size()){
        int y = G[x][i];
        if(y != F){
            DFS(y, lv + 1, x);
            subSize[x] += subSize[y];
        }
    }
}

void HLD(int curNode, int F)
{
    if(chainHead[chainNo] == -1){
        chainHead[chainNo] = curNode;
    }
    chainId[curNode] = chainNo;
    posInBase[curNode] = ++limit;
    baseArray[limit] = in[curNode];

    int sc = -1;
    for(int i=0;i<G[curNode].size();i++){
        int y = G[curNode][i];
        if(y == F) continue;
        if(sc == -1 || subSize[sc] < subSize[y]){
            sc = y;
        }
    }
    if(sc != -1){
        HLD(sc, curNode);
    }
    for(int i=0;i<G[curNode].size();i++){
        int y = G[curNode][i];
        if(y == F || sc == y) continue;
        chainNo++;
        HLD(y, curNode);
    }
}

void built_LCA()
{
    for(int j=1;(1 << j) <= n;j++){
        for(int i=1;i<=n;i++){
            if(LCA[i][j - 1]) LCA[i][j] = LCA[ LCA[i][j - 1] ][j - 1];
        }
    }
}

data Merge(data L, data R)
{
    data ret = data();
    Rep(i, 11) ret.cnt[i] = L.cnt[i] + R.cnt[i];
    return ret;
}

void built_tree(int node, int b, int e)
{
    if(b == e){
        Tree[node].cnt[ baseArray[b] ] = 1;
        return ;
    }
    int mid = b + e >> 1;
    int lf = node << 1;
    int rt = lf | 1;
    built_tree(lf, b, mid);
    built_tree(rt, mid + 1, e);
    Tree[node] = Merge(Tree[lf], Tree[rt]);
}

data query_tree(int node, int b, int e, int i, int j)
{
    if(b > j || e < i) {
        return data();
    }
    if(b >= i && e <= j) {
        return Tree[node];
    }
    int mid = b + e >> 1;
    int lf = node << 1;
    int rt = lf | 1;
    return Merge(query_tree(lf, b, mid, i, j), query_tree(rt, mid + 1, e, i, j));

}

void update_tree(int node, int b, int e, int i, int val)
{
    if(b > i || e < i) return ;
    if(b == e){
        Tree[node] = data();
        Tree[node].cnt[val] = 1;
        return ;
    }
    int mid = b + e >> 1;
    int lf = node << 1;
    int rt = lf | 1;
    update_tree(lf, b, mid, i, val);
    update_tree(rt, mid + 1, e, i, val);
    Tree[node] = Merge(Tree[lf], Tree[rt]);
}



int find_LCA(int x, int y)
{
    if(Level[x] < Level[y]) swap(x, y);
    int log = log2(Level[x]);
    for(int i=log;i>=0;i--){
         if(Level[x] - (1 << i) >= Level[y]){
            x = LCA[x][i];
         }
    }
    if(x == y) return x;
    for(int i=log;i>=0;i--){
        if(LCA[x][i] && LCA[x][i] != LCA[y][i]){
            x = LCA[x][i];
            y = LCA[y][i];
        }
    }
    return LCA[x][0];
}


data query_up(int u, int v)
{
    if(u == v) {
        data ret = data();
        ret.cnt[ in[u] ] = 1;
        return ret;
    }
    int uchain, vchain;
    data ans = data();
    uchain = chainId[u];
    vchain = chainId[v];
    while(true){
        uchain = chainId[u];
        if(uchain == vchain){
            ans = Merge(ans, query_tree(1, 1, limit, posInBase[v], posInBase[u]));
            break;
        }
        ans = Merge(ans, query_tree(1, 1, limit, posInBase[chainHead[uchain]], posInBase[u]));
        u = chainHead[uchain];
        u = LCA[u][0];
    }
    return ans;
}

data query(int x, int y)
{
    int lca = find_LCA(x, y);
    data a = query_up(x, lca);
    data b = query_up(y, lca);
    data mr = Merge(a, b);
    mr.cnt[ in[lca] ]--;
    return mr;
}


void update(int i, int val)
{
    in[i] = val;
    update_tree(1, 1, limit, posInBase[i], val);
}


int main()
{
//    fWrite;
    int t, qq = 1, qr;
    scani(t);
    while(t--) {
        scani2(n, qr);
        Clear();
        Rep(i, n) scani(in[i + 1]);
        Rep(i, n - 1) {
            int x, y;
            scani2(x, y);
//            x++; y++;
            G[x].pb(y);
            G[y].pb(x);
        }
        limit = chainNo = 0;
        DFS(1, 0, 0);
        HLD(1, 0);
        built_LCA();
        built_tree(1, 1, limit);
//        printf("Case %d:\n", qq++);
        while(qr--) {
            int typ, x, y;
            scani3(typ, x, y);
            if(typ) {
                data res = query(x, y);
                int mx = 0;
                Rep(i, 11) mx = max(mx, res.cnt[i]);
                write(mx);
            }
            else {
                update(x, y);
            }
        }
    }
    return 0;
}