Gao_on_a_tree.cpp

#include <bits/stdc++.h>
using namespace std;
// First you make it work, then you can always make it beautiful


class SegTree {
public:
    int len;
    vector<int> t;

    SegTree() : len(0) {}

    SegTree(int l) {
        len = l;
        t.assign(4 * len, -1);
    }

    void build(vector<int> &a, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(a, v << 1, tl, tm);
        build(a, (v << 1) + 1, tm + 1, tr);
        t[v] = max(t[v << 1], t[(v << 1) + 1]);
    }

    void update(int v, int tl, int tr, int id, int val) {
        if (tl == id && tr == id) {
            t[v] = val;
            return;
        }
        if (id < tl || id > tr) return;
        int tm = (tl + tr) >> 1;
        update(v << 1, tl, tm, id, val);
        update((v << 1) + 1, tm + 1, tr, id, val);
        t[v] = max(t[v << 1], t[(v << 1) + 1]);
    }

    int query(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l) return -1;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        int left = query(v << 1, tl, tm, l, r);
        int right = query((v << 1) + 1, tm + 1, tr, l, r);
        return max(left, right);
    }

    void build(vector<int> &a) {
        build(a, 1, 0, len - 1);
    }

    void update(int id, int val) {
        update(1, 0, len - 1, id, val);
    }

    int query(int l, int r) {
        return query(1, 0, len - 1, l, r);
    }
};

SegTree sg;
const int N = 1e5 + 5;
vector<int> adj[N];
vector<array<int, 3>> qry[N];
int val[N];

int sz[N];
int depth[N];
int par[N];
int top[N];
int heavy[N];
int pos[N];
int curr_pos;

void dfs(int node, int p, int d) {
    depth[node] = d;
    sz[node] = 1;
    int maxi = 0;
    par[node] = p;
    for(auto &j : adj[node]) if(j != p) {
        dfs(j, node, d + 1);
        sz[node] += sz[j];
        if(sz[j] > maxi) {
            maxi = sz[j];
            heavy[node] = j;
        }
    }
}

void decompose(int node, int t) {
    top[node] = t;
    pos[node] = curr_pos++;
    if(heavy[node] != -1) {
        decompose(heavy[node], t);
    }
    for(auto &j : adj[node]) if(j != par[node] && j != heavy[node]) {
        decompose(j, j);
    }
}

int query(int a, int b) {
    int res = -1;
    for (; top[a] != top[b]; b = par[top[b]]) {
        if(depth[top[a]] > depth[top[b]]) swap(a, b);
        int mx = sg.query(pos[top[b]], pos[b]);
        res = max(res, mx);
    }
    if(depth[a] > depth[b]) swap(a, b);
    int mx = sg.query(pos[a], pos[b]);
    res = max(res, mx);
    return res;
}

void solve() {
    int n, q;
    while((cin >> n >> q)) {

    for(int i=0;i<=n;i++) {
        adj[i].clear();
        qry[i].clear();
        heavy[i] = -1;
    }

    for(int i=1;i<=n;i++) cin >> val[i];
    for(int i=0;i<n-1;i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    curr_pos = 0;
    for(int i=0;i<=n;i++) {
        heavy[i] = -1;
    }
    dfs(1, 0, 0);
    decompose(1, 1);

    sg = SegTree(n);

    for(int i=0;i<q;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        qry[c].push_back({a, b, i});
    }

    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 1);
    sort(nodes.begin(), nodes.end(), [&](auto &a, auto &b) {
        return val[a] < val[b];
    });

    vector<int> ans(q);

    int ptr = 0;
    for(int i=0;i<=n;i++) {
        if(qry[i].empty()) continue;
        while(ptr < n && val[nodes[ptr]] <= i) {
            sg.update(pos[nodes[ptr]], val[nodes[ptr]]);
            ptr++;
        }
        for(auto &[a, b, id] : qry[i]) {
            int mx = query(a, b);
            if(mx == i) {
                ans[id] = 1;
            }
        }
    }

    for(int i=0;i<q;i++) {
        if(ans[i]) cout << "Find\n";
        else cout << "NotFind\n";
    }
    
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}