Submission #538793

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <map>
#include <cassert>
#include <set>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

struct Tree {
    typedef Tree* NP;
    NP l, r;
    struct Node {
        Node(int sz = 0) : sz(sz), lzf(false) {}
        int sz;
        int mi;
        bool lzf;
    } n;
    Tree() {}
    Tree(int sz, int hev[], int hevsm[], int data[]) : n(sz) {
        if (sz == 1) {
            lzdata(data[0]);
            return;
        }
        int sm = hevsm[sz] - hevsm[0];
        int md = lower_bound(hevsm, hevsm+sz-1, sm/2+hevsm[0]) - hevsm;
        l = new Tree(md, hev, hevsm, data);
        r = new Tree(sz - md, hev+md, hevsm+md, data+md);
        update();
    }
    void lzdata(int d) {
        n.mi = d;
    }
    void update() {
        n.mi = min(l->n.mi, r->n.mi);
    }
    void push() {
        if (n.sz == 1) return;
    }
    int searchl(int a, int b, int x) {
        if (b <= 0 || n.sz <= a) {
            return x;
        }
        if (n.sz == 1) {
            return x % n.mi;
        }
        if (x < n.mi) return x;
        return r->searchl(a - l->n.sz, b - l->n.sz, l->searchl(a, b, x));
    }
    int searchr(int a, int b, int x) {
        if (b <= 0 || n.sz <= a) {
            return x;
        }
        if (n.sz == 1) {
            return x % n.mi;
        }
        if (x < n.mi) return x;
        return l->searchr(a, b, r->searchr(a - l->n.sz, b - l->n.sz, x));
    }
};

template <int N>
struct HLComp_Y {
    vector<int> g[N];

    P n2l[N]; //node to line (line id - line pos)
    int lc;
    Tree *li[N]; //line data
    P l2p[N]; //line to parent
    int sz[N]; //node size

    int data[N]; // my data

    int buf[N]; // buffer of sz - sz[child]
    int bufsm[N+1];
    int bufdata[N]; // buffer of mydata
    int ldps[N]; // line dps

    void add(int a, int b) {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    void dfs_sz(int p, int b) {
        sz[p] = 1;
        for (int d: g[p]) {
            if (d == b) continue;
            dfs_sz(d, p);
            sz[p] += sz[d];
        }
    }
    void dfs(int p, int b) {
        if (g[p].size() == (b == -1 ? 0 : 1)) {
            // make line
            buf[n2l[p].second] = 1;
            bufdata[n2l[p].second] = data[p];
            bufsm[n2l[p].second+1] = bufsm[n2l[p].second] + buf[n2l[p].second];
            li[n2l[p].first] = new Tree(n2l[p].second+1, buf, bufsm, bufdata);
            return;
        }
        int ma = -1, md = -1;
        for (int d: g[p]) {
            if (d == b) continue;
            if (ma < sz[d]) {
                ma = sz[d];
                md = d;
            }
        }
        n2l[md] = P(n2l[p].first, n2l[p].second+1);
        buf[n2l[p].second] = sz[p]-sz[md];
        bufdata[n2l[p].second] = data[p];
        bufsm[n2l[p].second+1] = bufsm[n2l[p].second] + buf[n2l[p].second];
        dfs(md, p);
        for (int d: g[p]) {
            if (d == b) continue;
            if (d == md) continue;
            n2l[d] = P(lc, 0);
            l2p[lc] = n2l[p];
            ldps[lc] = ldps[n2l[p].first]+1;
            lc++;
            dfs(d, p); // light
        }
    }
    void init() {
        n2l[0] = P(0, 0);
        l2p[0] = P(-1, 0);
        ldps[0] = 0;
        bufsm[0] = 0;
        lc = 1;
        dfs_sz(0, -1);
        dfs(0, -1);
    }
    // void data_set(int k, int x) {
    //     li[n2l[k].first]->set(n2l[k].second, x);
    // }
    int lca_line(int u, int v) {
        int xl = n2l[u].first;
        int yl = n2l[v].first;
        if (ldps[xl] < ldps[yl]) swap(xl, yl);
        while (ldps[xl] > ldps[yl]) {
            xl = l2p[xl].first;
        }
        while (xl != yl) {
            xl = l2p[xl].first;
            yl = l2p[yl].first;
        }
        return xl;
    }

    vector<P> ybuf;
    int path_get(int u, int v, int x) {
        int xl, xp; tie(xl, xp) = n2l[u];
        int yl, yp; tie(yl, yp) = n2l[v];
        int lc = lca_line(u, v);
        while (xl != lc) {
            x = li[xl]->searchr(0, xp+1, x);
            tie(xl, xp) = l2p[xl];            
        }
        int yyl = yl, yyp = yp;
        while (yyl != lc) {
            tie(yyl, yyp) = l2p[yyl];
        }
        if (xp > yyp) {
            x = li[xl]->searchr(yyp, xp+1, x);
        } else {
            x = li[yyl]->searchl(xp, yyp+1, x);
        }
        vector<P> ybuf;
        while (yl != lc) {
            ybuf.push_back(P(yl, yp));
            tie(yl, yp) = l2p[yl];
        }
        reverse(ybuf.begin(), ybuf.end());
        for (P p: ybuf) {
            x = li[p.first]->searchl(0, p.second+1, x);
        }
/*        while (yl != lc) {
            x = li[yl]->searchl(0, yp+1, x);
            tie(yl, yp) = l2p[yl];
        }*/

        return x;
    }
};


const int MN = 100100;
HLComp_Y<MN> hl;


int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> hl.data[i];
    }

    for (int i = 0; i < n-1; i++) {
        int b, c;
        cin >> b >> c; b--; c--;
        hl.add(b, c);
    }
    hl.init();
    for (int i = 0; i < q; i++) {
        int x, v, w;
        cin >> x >> v >> w; v--; w--;
        cout << hl.path_get(v, w, x) << endl;
    }
	return 0;
}

Submission Info

Judge Result