救救萌新qwq自闭惹

AC#1 , #3 , #4 , #8，其他WA掉...不清楚哪里出锅惹qwq大佬们救救蒟蒻

#include<bits/stdc++.h>
using namespace std;
struct item
{
    unsigned long long lef0 , lef1 , rig0 , rig1;
} c[800000] , ans1[200000] , ans2[200000];
int n , m , k , siz[200000] , fa[200000] , hson[200000] , maxx[200000];
int fst[400000] , nex[400000] , v[400000] , tot , x , y , qaq , dep[200000] , qwq;
int top[200000] , id[200000] , pl[200000] , f[200000];
unsigned long long truee , s[200000] , z;
void add( int x , int y )
{
    nex[++tot] = fst[x];
    fst[x] = tot;
    v[tot] = y;
}
int dfs1( int u , int fath )
{
    dep[u] = dep[fath] + 1;
    fa[u] = fath;
    for(int i = fst[u] ; i ; i = nex[i] )
    {
        if(v[i] == fath)
        continue;
        siz[u] += dfs1(v[i] , u) + 1;
        if(siz[v[i]] >= maxx[u])
        {
            maxx[u] = siz[v[i]];
            hson[u] = v[i];
        }
    }
    return siz[u];
}
void dfs2( int u , int t )
{
    if(!u)
    return ;
    top[u] = t;
    id[u] = ++tot;
    pl[tot] = u;
    dfs2(hson[u] , t);
    for(int i = fst[u] ; i ; i = nex[i] )
    {
        if(v[i] == fa[u] || v[i] == hson[u])
        continue;
        dfs2(v[i] , v[i]);
    }
    return ;
}
unsigned long long do_( unsigned long long a , int k )
{
    if(f[k] == 1)
    return a & s[k];
    if(f[k] == 2)
    return a | s[k];
    return a ^ s[k];
}
item push_up( item a , item b )
{
    item ans;
    ans.lef0 = (((~a.lef0) & b.lef0) + (a.lef0 & b.lef1));
    ans.lef1 = (((~a.lef1) & b.lef0) + (a.lef1 & b.lef1));
    ans.rig0 = (((~b.rig0) & a.rig0) + (b.rig0 & a.rig1));
    ans.rig1 = (((~b.rig1) & a.rig0) + (b.rig1 & a.rig1));
    return ans;
}
void build( int l , int r , int id )
{
    if(l == r)
    {
        c[id].lef0 = c[id].rig0 = do_(0 , pl[l]);
        c[id].lef1 = c[id].rig1 = do_(truee , pl[l]);
        return ;
    }
    int mid = (l + r) >> 1;
    build(l , mid , id << 1);
    build(mid + 1 , r , id << 1 | 1);
    c[id] = push_up(c[id << 1] , c[id << 1 | 1]);
//    cout << id << " " << c[id].lef0 << " " << c[id].lef1 << " " << c[id].rig0 << " " << c[id].rig1 << "qwq\n";
    return ;
}
void fix( int l , int r , int a , int id )
{
    if(l > a || r < a)
    return ;
    if(l == r && r == a)
    {
        c[id].lef0 = c[id].rig0 = do_(0 , pl[l]);
        c[id].lef1 = c[id].rig1 = do_(truee , pl[l]);
        return ;
    }
    int mid = (l + r) >> 1;
    fix(l , mid , a , id << 1);
    fix(mid + 1 , r , a , id << 1 | 1);
    c[id] = push_up(c[id << 1] , c[id << 1 | 1]);
    return ;
}
item que( int l , int r , int a , int b , int id )
{
    if(a <= l && r <= b)
    return c[id];
    int mid = (l + r) >> 1;
    if(mid >= b)
    return que(l , mid , a , b , id << 1);
    if(mid < a)
    return que(mid + 1 , r , a , b , id << 1 | 1);
    return push_up(que(l , mid , a , b , id << 1) , que(mid + 1 , r , a , b , id << 1 | 1));
}
unsigned long long sc( int x , int y , unsigned long long z )
{
    int fx = top[x] , fy = top[y] , cnt1 = 0 , cnt2 = 0;
    item ans = (item){0 , truee , 0 , truee};
    while(fx != fy)
    {
        if(dep[fx] > dep[fy])
        {
            ans1[++cnt1] = que(1 , n , id[fx] , id[x] , 1);
            x = fa[fx];
            fx = top[x];
        }
        else
        {
            ans2[++cnt2] = que(1 , n , id[fy] , id[y] , 1);
            y = fa[fy];
            fy = top[y];
        }
    }
    if(dep[x] > dep[y])
    ans1[++cnt1] = que(1 , n , id[y] , id[x] , 1);
    else
    ans2[++cnt2] = que(1 , n , id[x] , id[y] , 1);
    for(int i = 1 ; i <= cnt2 ; i++ )
    {
        swap(ans1[i].lef0 , ans1[i].rig0);
        swap(ans1[i].lef1 , ans1[i].rig1);
    }
    for(int i = 1 ; i <= cnt1 ; i++ )
    {
        ans = push_up(ans , ans1[i]);
    }
    for(int i = cnt2 ; i >= 1 ; i-- )
    {
        ans = push_up(ans , ans2[i]);
    }
//    cout << ans.lef0 << " " << ans.lef1 << " " << ans.rig0 << " " << ans.rig1 << "\n";
    unsigned long long anss = 0 , t = 1;
    t <<= (k - 1);
    for(int i = k - 1 ; i >= 0 ; i-- )
    {
        if(ans.lef0 & t)
        anss += t;
        else if(z >= t && ans.lef1 & t)
        {
            z -= t;
            anss += t;
        }
        t >>= 1;
    }
    return anss;
}
int main()
{
    cin >> n >> m >> k;
    truee = (~truee) >> (64 - k);
    for(int i = 1 ; i <= n ; i++ )
    {
        scanf("%d%llu" , &f[i] , &s[i]);
    }
    for(int i = 1 ; i < n ; i++ )
    {
        scanf("%d%d" , &x , &y);
        add(x , y);
        add(y , x);
    }
    tot = 0;
    dep[1] = 0;
    dfs1(1 , 1);
    dfs2(1 , 1);
    tot = 0;
    build(1 , n , 1);
    for(int i = 1 ; i <= m ; i++ )
    {
        scanf("%d%d%d%llu" , &qaq , &x , &y , &z);
        if(qaq == 1)
        {
            printf("%llu\n" , sc(x , y , z));
        }
        if(qaq == 2)
        {
            f[id[x]] = y;
            s[id[x]] = z;
            fix(1 , n , id[x] , 1);
        }
    }
    return 0;
}