#美团笔试#
第三题我的解法：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<stdlib.h>
#include<cstring>
#include<algorithm>
#include<map>
#include<unordered_map>
using namespace std;

vector<int>dfs(vector<int>a,vector<vector<int>>edge, int pre, int cur, int goal)
{
    if (cur == goal) return { cur };
    for (int i = 0; i < edge[cur].size(); i++)
    {
        int p = edge[cur][i];
        if (p == pre)continue;
        vector<int>sub = dfs(a, edge, cur, p, goal);
        if (sub.size() != 0)
        {
            sub.push_back(cur);
            return sub;
        }
    }
    return {};
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int>a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<vector<int>>edge(n + 1);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for (int i = 0; i < m; i++)
    {
        int x, u, v;
        cin >> x >> u >> v;
        if (x == 1)
        {
            vector<int>road = dfs(a, edge, 0, u, v);
            for (int i=0;i<road.size();i++)
            {
                int num = road[i];
                a[num] = a[num] ? 0 : 1;
            }
        }
        if (x == 2)
        {
            vector<int>road = dfs(a, edge, 0, u, v);
            int ans = 0;
            int flag = 1;
            for (int i = 0; i < road.size(); i++)
            {
                ans += a[road[i]] * flag;
                flag *= 2;
            }
            cout << ans << endl;
        }
    }
    return 0;
}