(text{Solution})
又是一道考场想到做法写不出来的题
对于 (ge x) 的数全部 (+1) 的操作有个很优美的大材小用的想法，那就是分段函数
于是线段树倒着维护分段函数，为了快速统计，要记录线段树结点中每个点跳出本结点的值，vector 记下排序
于是区间可以拆成 (log) 段，每段二分 (log) 统计，注意到从后往前，拆开后分段函数不能合并，不然复杂度会错，但可以找到最大的值使得它扔进函数出来后 (le k)，这需要在分段函数上二分更新，每个拆开后的区间更新一次
那么在树上就硬套个树剖，(O(n log n+qlog^3n))，恶心的是树上路径要维护向上和下的分段函数，记录的信息也要对应多维护，比较繁琐
但是 (log^3) 过掉 (2times 10^5) 也是厉害的
正解当然得正确点 (O(nlog n+qlog^2n))
考虑这个困难的操作，仍然是可以更巧妙地弄出最后有哪些数的
倒着加数 (x) ，每次新加的数受之前加的数影响，可以发现新加的数就是当前自然数集合从小到大没有加入过的第 (x) 个
那这样就可以简单的线段树上二分得到了
然后硬上树剖，考虑拆段后询问应该怎么处理
只有一个段时直接查询 (le k) 的数有多少，记为 (p)，那么下一个段就要查询 (le k-p) 的数有多少了
仍然是要维护向上和向下信息的
代码当然是写了恶心的做法，毕竟考场上写了 (4Kb) 怎么可以弃掉
(text{Code})
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #define eb emplace_back using namespace std; template <typename Tp> void read(Tp &x) { x = 0; char ch = getchar(); int f = 0; for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar()); for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar()); if (f) x = ~x + 1; } const int N = 2e5 + 5, inf = 4e5; int n, m, a[N]; vector<int> G[N]; int fa[N], dfn[N], sz[N], dfc, top[N], dep[N], son[N], ed[N], rev[N]; void dfs1(int x) { sz[x] = 1, dep[x] = dep[fa[x]] + 1; for(auto v : G[x]) { if (v == fa[x]) continue; fa[v] = x, dfs1(v), sz[x] += sz[v], son[x] = (sz[son[x]] < sz[v] ? v : son[x]); } } void dfs2(int x, int t) { top[x] = t, ed[t] = x, dfn[x] = ++dfc, rev[dfc] = x; if (son[x]) dfs2(son[x], t); for(auto v : G[x]) { if (v == fa[x] || v == son[x]) continue; dfs2(v, v); } } struct node{int a, b;}; typedef vector<node> Vec; vector<node> seg[2][N * 19]; vector<int> vec[2][N * 19]; int ls[N * 19], rs[N * 19], size, R[N], rt[N]; int MaxDefine(Vec &seg, int z){return (z == seg.size() - 1) ? inf : seg[z + 1].a - 1;} void Merge(Vec &c, Vec &a, Vec &b) { for(int i = 0, j = 0; i < a.size(); i++) { while (MaxDefine(b, j) < a[i].a + a[i].b) ++j; int now = a[i].a; while (j < b.size()) { c.eb(node{now, a[i].b + b[j].b}); if (MaxDefine(b, j) >= MaxDefine(a, i) + a[i].b) break; now = MaxDefine(b, j) + 1 - a[i].b, ++j; } } } void Merge(vector<int> &a, vector<int> &b) { int i = 0, j = 0, k = 0; vector<int> c(a.size() + b.size()); while (i < a.size() && j < b.size()) if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; while (i < a.size()) c[k++] = a[i++]; while (j < b.size()) c[k++] = b[j++]; swap(a, c); } void merge(vector<int> &a, vector<int> &b, Vec &c) { vector<int> d(b.size()); for(int i = 0, j = 0; i < b.size(); i++) { while (MaxDefine(c, j) < b[i]) ++j; d[i] = b[i] + c[j].b; } Merge(a, d); } void build(int t, int &p, int l, int r) { if (!p) p = ++size; if (l == r) { int now = a[rev[l + dfn[t] - 1]]; for(int j = 0; j < 2; j++) seg[j][p].eb(node{0, 0}), seg[j][p].eb(node{now, 1}), vec[j][p].eb(now); return; } int mid = l + r >> 1; build(t, ls[p], l, mid), build(t, rs[p], mid + 1, r); Merge(seg[0][p], seg[0][rs[p]], seg[0][ls[p]]), Merge(seg[1][p], seg[1][ls[p]], seg[1][rs[p]]); merge(vec[0][p] = vec[0][ls[p]], vec[0][rs[p]], seg[0][ls[p]]); merge(vec[1][p] = vec[1][rs[p]], vec[1][ls[p]], seg[1][rs[p]]); } void build(int t){R[t] = dfn[ed[t]] - dfn[t] + 1, build(t, rt[t], 1, R[t]);} void calc(Vec &seg, int &x) { int l = 0, r = seg.size() - 1, mid = l + r >> 1, z; for(; l <= r; mid = l + r >> 1) if (MaxDefine(seg, mid) >= x) z = mid, r = mid - 1; else l = mid + 1; x += seg[z].b; } int count(vector<int> &vec, int k) { int l = 0, r = vec.size() - 1, mid = l + r >> 1, z = -1; for(; l <= r; mid = l + r >> 1) if (vec[mid] <= k) z = mid, l = mid + 1; else r = mid - 1; return z + 1; } void update(int &Mx, Vec &seg) { int l = 0, r = seg.size() - 1, mid = l + r >> 1, z = 0; for(; l <= r; mid = l + r >> 1) if (seg[mid].a + seg[mid].b <= Mx) z = mid, l = mid + 1; else r = mid - 1; if (MaxDefine(seg, z) + seg[z].b <= Mx) Mx = MaxDefine(seg, z); else Mx -= seg[z].b; } int Query(int p, int fl, int l, int r, int x, int y, int &Mx) { if (!p || x > r || y < l || x > y) return 0; if (x <= l && r <= y){ int res = count(vec[fl][p], Mx); update(Mx, seg[fl][p]); return res; } int mid = l + r >> 1, res = 0; if (!fl) { if (x <= mid) res = Query(ls[p], fl, l, mid, x, y, Mx); if (y > mid) res += Query(rs[p], fl, mid + 1, r, x, y, Mx); } else { if (y > mid) res = Query(rs[p], fl, mid + 1, r, x, y, Mx); if (x <= mid) res += Query(ls[p], fl, l, mid, x, y, Mx); } return res; } int LCA(int x, int y) { while (top[x] ^ top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]]; } return (dep[x] < dep[y] ? x : y); } int solve(int u, int v, int k) { int w = LCA(u, v), res = 0, Mx = k; while (top[v] != top[w]) res += Query(rt[top[v]], 1, 1, R[top[v]], 1, dfn[v] - dfn[top[v]] + 1, Mx), v = fa[top[v]]; res += Query(rt[top[w]], 1, 1, R[top[w]], dfn[w] - dfn[top[w]] + 1, dfn[v] - dfn[top[w]] + 1, Mx); vector<int> d; while (top[u] != top[w]) d.eb(u), u = fa[top[u]]; if (dep[u] > dep[w]) res += Query(rt[top[w]], 0, 1, R[top[w]], dfn[w] - dfn[top[w]] + 2, dfn[u] - dfn[top[w]] + 1, Mx); for(int i = (int)d.size() - 1; ~i; i--) res += Query(rt[top[d[i]]], 0, 1, R[top[d[i]]], 1, dfn[d[i]] - dfn[top[d[i]]] + 1, Mx); return res; } int main() { freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); int t; read(n), read(m), read(t); for(int i = 1; i <= n; i++) read(a[i]); for(int i = 1, u, v; i < n; i++) read(u), read(v), G[u].eb(v), G[v].eb(u); dfs1(1), dfs2(1, 1); for(int i = 1; i <= n; i++) if (top[i] == i) build(i); for(int i = 1, u, v, k, lst = 0; i <= m; i++) read(u), read(v), read(k), u ^= (lst * t), v ^= (lst * t), k ^= (lst * t), printf("%dn", lst = solve(u, v, k)); } 
