D7lsu. 树题

\(\text{Solution}\)

又是一道考场想到做法写不出来的题
对于 \(\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\) 怎么可以弃掉

\(\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("%d\n", lst = solve(u, v, k));
}