又是一道考場想到做法寫不出來的題
對於 \(\ge x\) 的數全部 \(+1\) 的操作有個很優美的大材小用的想法，那就是分段函數
於是線段樹倒著維護分段函數，為了快速統計，要記錄線段樹結點中每個點跳出本結點的值，vector 記下排序
於是區間可以拆成 \(\log\) 段，每段二分 \(\log\) 統計，注意到從後往前，拆開後分段函數不能合併，不然複雜度會錯，但可以找到最大的值使得它扔進函數出來後 \(\le k\)，這需要在分段函數上二分更新，每個拆開後的區間更新一次
那麼在樹上就硬套個樹剖，\(O(n \log n+q\log^3n)\)，噁心的是樹上路徑要維護向上和下的分段函數，記錄的資訊也要對應多維護，比較繁瑣
但是 \(log^3\) 過掉 \(2\times 10^5\) 也是厲害的
正解當然得正確點 \(O(n\log n+q\log^2n)\)
考慮這個困難的操作，仍然是可以更巧妙地弄出最後有哪些數的
倒著加數 \(x\) ，每次新加的數受之前加的數影響，可以發現新加的數就是當前自然數集合從小到大沒有加入過的第 \(x\) 個
那這樣就可以簡單的線段樹上二分得到了
然後硬上樹剖，考慮拆段後詢問應該怎麼處理
只有一個段時直接查詢 \(\le k\) 的數有多少，記為 \(p\)，那麼下一個段就要查詢 \(\le k-p\) 的數有多少了
仍然是要維護向上和向下資訊的
程式碼當然是寫了噁心的做法，畢竟考場上寫了 \(4Kb\) 怎麼可以棄掉
#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("%d\n", lst = solve(u, v, k));
}