Types of problems that can be solved
The problems that this Trick can solve are as follows:
- Given\(n\)nodesRooted, boundless and a little powerfulTree.
- have\(m\)queries, each query is shaped like a dot\(x\)ofwithin subtreeand\(x\) Depth differenceno more than\(k\)The extreme value/rank/sum of the points.
- \(O(n\,log\,n)\)Can pass.
Advantages and Disadvantages
Advantages: Can be forced online, the code is simple.
Disadvantages: It may be stuck (the probability is very small).
Ideas
First, the depth difference does not exceed\(k\)This limitation is difficult to deal with. We cannot use one-dimensional numbers to connect these points, and there is no difference method.
So - 2D, start!
Let's count one\(x\)Become a point on a two-dimensional plane:\((depp_x\,,dfn_x)\)。
So for a point\(p\)The query becomes the abscissa at\([depp_p\,,depp_p+k]\), the ordinate is in\([dfn_p\,,dfn_p+sz_p-1]\)The extreme value/rank/sum of the points.
Obviously this can be done by using trees within trees, but\(O(n\,log^2\,n)\), is there a better way?
We consider the chairman tree, but the chairman tree must satisfyReducibility, while the best value does not.
However, when the abscissa of a point belongs to \([1,depp_p-1]\) When , his vertical coordinate must not belong to \([depp_p\,,dep_p+k]\), that is to sayWe do not need to subtract two line segment trees, so the question does not need to satisfy subtractability.
So we can happily get to the point.
Algorithm process
- Use a dfs to find the value of each node\(dfn,sz,depp\)。
- Sort the nodes according to depth, add them to the chairman tree one by one, and recordThe subscript of the root of the chair tree for the last lesson of each depth \(idx\)。
Example code
The code of this Trick basically doesn’t change for each question, just apply it directly.
CF893F Subtree Minimum Query
using namespace std;
#define midd ((node[u].l + node[u].r) >> 1)
constexpr int maxn = 100010;
int n, r, m, v[maxn], a, b, dfn[maxn], nowdfn, depp[maxn], s[maxn], idx[maxn], sz[maxn], lans, maxdep = 0;
vector G[maxn];
struct nodee {
int v, l, r, ls, rs;
} ;
struct tr {
nodee node[maxn << 5];
int root[maxn], cnt;
void build(int &u, int l, int r) {
u = ++cnt;
node[u] = {1000000000, l, r, 0, 0};
if (l == r) return;
build(node[u].ls, l, midd);
build(node[u].rs, midd + 1, r);
return ;
}
void update(int &u, int pree, int x, int k) {
u = ++cnt;
node[u] = node[pree];
node[u].v = min(node[u].v, k);
if (node[u].l == node[u].r) return ;
if (x <= midd) update(node[u].ls, node[pree].ls, x, k);
else update(node[u].rs, node[pree].rs, x, k);
return ;
}
int query(int u, int l, int r) {
if (node[u].l >= l && node[u].r <= r) return node[u].v;
int ress = 1000000000;
if (l <= midd) ress = min(query(node[u].ls, l, r), ress);
if (r > midd) ress = min(query(node[u].rs, l, r), ress);
return ress;
}
}t;
void dfs(int u, int fa) {
sz[u] = 1;
dfn[u] = ++nowdfn;
for (int now : G[u]) {
if (now == fa) continue;
depp[now] = depp[u] + 1;
maxdep = max(maxdep, depp[now]);
dfs(now, u);
sz[u] += sz[now];
}
return ;
}
signed main() {
ios::sync_with_stdio(false), (nullptr), (nullptr);
cin >> n >> r;
depp[r] = 1;
for (int i = 1; i <= n; i++) {
s[i] = i;
cin >> v[i];
}
for (int i = 1; i < n; i++) {
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(r, 0);
sort(s + 1, s + 1 + n, [](int a, int b){return depp[a] < depp[b];});
//The above is the first part dfs
([0], 1, n);
idx[0] = [0];
for (int i = 1; i <= n; i++) {
([i], [i - 1], dfn[s[i]], v[s[i]]);
if (depp[s[i]] != depp[s[i + 1]]) idx[depp[s[i]]] = i;
}
//The above is the second part, chairman tree preprocessing
cin >> m;
while (m--) {
cin >> a >> b;
a = (a + lans) % n + 1;
b = (b + lans) % n;
lans = ([idx[min(maxdep, depp[a] + b)]], dfn[a], dfn[a] + sz[a] - 1);
cout << lans << '\n';
}
return 0;
}