iiitv/ChefLib

//Solution by ista2000
//Original solution link: https://www.codechef.com/viewsolution/13585707
#include <bits/stdc++.h>
#define int long long int
using namespace std;

int n, q, r, key;
//Solution uses a persistent trie to solve this problem, all the function names are self-explanatory
struct trie
{
    int nxt[2];
    trie()
    {
        nxt[0] = nxt[1] = -1;
    }
}ar[300002 * 32];//This is the trie, ar[i] is a node in the trie
int tot = 0;
void insert(int x, int root)
{
    int i = 32;
    while(i--)
    {
        int b = (bool)(x & (1 << i));
        if(ar[root].nxt[b] == -1)
        {
            ar[++tot] = trie();
            ar[root].nxt[b] = tot;
        }
        else
        {
            ar[++tot] = ar[ar[root].nxt[b]];
            ar[root].nxt[b] = tot;
        }
        root = ar[root].nxt[b];
    }
}
map<int, vector< pair<int,int> > > g;
map<int, int> start;
void dfs(pair<int,int> u, pair<int,int> p)
{
    ar[++tot] = ar[ start[p.first] ];
    start[u.first] = tot;
    insert(u.second, start[u.first]);
    for(pair<int,int> v: g[u.first])
        dfs(v, u);
}
void addnode(int v, int u, int k)
{
    ar[++tot] = ar[ start[v] ];
    start[u] = tot;
    insert(k, start[u]);
}

int maxxor(int x, int root)
{
    int i = 32, ret = 0;
    while(i--)
    {
        int b = (bool)(x & (1 << i));
        if(ar[root].nxt[b ^ 1]==-1)
            root = ar[root].nxt[b];
        else
            ret += 1 << i, root = ar[root].nxt[b ^ 1];
    }
    return ret;
}
int minxor(int x, int root)
{
    int i = 32, ret = 0;
    while(i--)
    {
        int b = (bool)(x & (1 << i));
        if(ar[root].nxt[b]==-1)
            ret += 1 << i, root = ar[root].nxt[b ^ 1];
        else
            root = ar[root].nxt[b];
    }
    return ret;
}

#undef int
int main()
{
#define int long long int

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q >> r >> key;
    for(int i = 0;i<n-1;i++)
    {
        int u, v, k;
        cin >> u >> v >> k;
        g[v].push_back({u, k});
    }
    ar[0] = trie();
    start[0] = 0;
    tot = 0;
    dfs( {r, key}, {0, 0});
    int la = 0;
    while(q--)
    {
        int t;
        cin >> t;
        t ^= la;
        if(t == 0)
        {
            int u, v, k;
            cin >> v >> u >> k;
            v ^= la;
            u ^= la;
            k ^= la;
            addnode(v, u, k);
        }
        else
        {
            int u, k;
            cin >> u >> k;
            u ^= la;
            k ^= la;
            int ans1 = maxxor(k, start[u]);
            int ans2 = minxor(k, start[u]);
            la = ans1 ^ ans2;
            cout << ans2 << " " << ans1 << endl;
        }
    }

    return 0;
}