PROBLEM LINK:
Setter- Kirill Gulin
Tester- Ivan Safonov
Editorialist- Abhishek Pandey
DIFFICULTY:
Hard
PRE-REQUISITES:
Persistent Segment Tree, Dynamic Programming approach to find Least Common Ancestor (LCA) of two nodes, DFS
PROBLEM:
We are given a tree with N nodes - each node having a value val_i. We have to answer Q queries where each query will give us k nodes (u_1,u_2,..,u_k) and a value r. We need to tell the minimum of |val_u-r| where val_u is the value of a node lying in path covering all the given k nodes.
QUICK EXPLANATION:
Key to Success- Practice of Persistent Segment Trees was needed. Labeling nodes of segment tree by depth[node] can potentially make things quite simple.
Sort the query nodes in order of DFS traversal. Also, make a duplicate array val which stores the values, and the nodes to which the values correspond, in sorted order. The answer for a query, after sorting nodes in order of DFS, is union of paths from u_i to LCA(u_i,u_{(i+1)\%N}). Queries are hence reduced to, in a path from u to LCA(u_i,u_{(i+1)\%N}), find the val closest to r.
To answer these make a persistent segment tree of all nodes, the tree storing the depth of nodes for the version they were made (or, they will store some random garbage value if they are “useless” node for that version). As we will see in editorial depth is non-increasing for a version of tree, a simple check of depth[node] \ge depth[LCA(u_i,u_{(i+1)\%N})] can confirm that the node lies in the path.
Now, find an index j in val such that is closest to r. We now break the queries into 2 groups, one will try to find the greatest possible index in range [1,j-1] so that node corresponding to value at that index lies in path. The other part will try to find the smallest possible value in range [j,N] similarly.We pick the one giving lesser value out of the two as answer. These queries are repeated k times so that all nodes in S get covered
EXPLANATION:
This editorial is going to be a bit exhaustive. It is expected that you guys are aware of the concept of persistence, as well as the idea of finding LCA of two nodes in O(LogN) time. If thats not the case, please head over to links in pre-requisites first. We will be primarily discussing setter’s solution, and breaking/modularising this editorial with respect to each step required to get AC.
1. Pre-Processing-
The first thing to do, is to make a pair of < val_u,u > where val_u is the value of node u. Now, sort it. We will be making segment tree over this val array. Before moving on, compress/map the value of indices of val_u from original array to sorted array. Meaning, make a table which tells you "The value which was at index u in original array is at index v in sorted val array."
An illustration of making this table is in tabs-
Click to view
for(int i = 0; i < n; ++i) {
num[vals[i].second] = i;//vals[i].second=u (the index in original array)
}
The above table will be used in making and querying over the segment tree, as it can be used during DFS of a node to find directly at which index of val array the current node corresponds to.
Also, the queries dont guarantee that nodes will be in order of DFS, they can be in any random order! Hence, we will need to sort them in order of DFS , for which we need to do a Euler tour of tree and calculate in-time and out-time of all nodes.
2. What to store in the segment tree?
We will be storing depths of the nodes in the tree. Why? That cannot be answered right now. It wont make sense until we grasp concept of constructing and updating the tree. But for now, just know that it is very useful in querying.
The parent-child relation is, parent will store the the greater value of depth. In other words, if our segment tree array is t[], then the relation is-
t[v] = max(t[lson[v]], t[rson[v]]);//lson=left son. rson=right son
The leaves will simple store depth of the node for which the segment tree is made - only for valid index in val array. (Meaning, the range [l,r] of leaf must follow l=r=ind where ind is index of that node in val array).
3. Constructing and Updating the tree, along with concepts involved-
First let me describe the procedure, and then we will move over to the concept.
Start a DFS from the root. Make a complete segment tree for the root or input tree, and for rest of nodes, add a new root, and consequently logN new nodes to cover its path from root to leaves. (The concept of persistence). This means that, for root node, build() function will be invoked, while for other N-1 nodes, we will update the tree by adding logN new nodes on path from root of segment tree to valid/corresponding leaf.
I should highlight how these newly added nodes point to the children for those weak in the topic. You can refer to tab below.
Click to view
REMEMBER- We are adding nodes corresponding to path from root to corresponding leaf. Now, a segment tree has 2 children. Obviously, we will be adding only 1 new child for a node (we are tracing a path to leaf). What about the other child? It will point to the child of older segment tree!! Meaning, say this other child is the right child, we will make make this right child point to right child of corresponding node in previous version of the tree."
Now, coming to the reasoning part. The first question is why store depth in segment tree. Remember that when we update to add new nodes, the new nodes can either point to a newly created child of current version, or point to a child from older version. It cannot point to a child of newer version as we are not modifying old nodes - instead we are creating new ones. Hence note that, depth of a node is maximum and root and may decrease as we go till leaves.
Hence, for now just say that I need a path from node u to node v. What will it look like? We will go from u to LCA(u,v) and from there to v. Since depth is non-increasing, a simple check of depth[node] \ge depth[LCA(u,v)] is a sufficient check that the current node of segment tree is holding information about path from u to LCA(u,v) etc. We query segment tree of u for this, and get info about path from u to LCA(u,v).
The above paragraph is the million dollar one here. If you understand this, understanding setter’s solution and concept is a breeze.
Now, lets discuss implementing. For build function, we have to build entire segment tree for root node of tree. If we arrive at the correct leaf node (for which l=r=ind where ind is index in val array) then we update the leaf node by depth, else we leave it empty. The relation between parent and child nodes stay the same. Can you try writing the build function? For your reference, its given in tab-
Click to view
int build(int tl, int tr, int index, int value) {
int v = newNode();//Returns index of new node in tree. Its like, tree[v] is newly created node.
if (tl == tr) {
if (index == tl) t[v] = value;//Valid range
return v;
}
int tm = (tl + tr) / 2;
lson[v] = build(tl, tm, index, value);
rson[v] = build(tm + 1, tr, index, value);
t[v] = max(t[lson[v]], t[rson[v]]);
return v;
}
Also, now that you have done build function, try the update one as well (especially if you failed in framing build function yourself). The logic is similar. We create a new root, then create LogN new nodes for path from root to corresponding leaves. The new nodes can point to children of current version (if created) or older versions. The function is given in tab below-
Click to view
int update(int v, int idx, int val, int tl, int tr) {
int u = newNode();
if (tl == tr) {
t[u] = val;
return u;
}
int tm = (tl + tr) / 2;
if (idx <= tm) {
lson[u] = update(lson[v], idx, val, tl, tm);
rson[u] = rson[v];
} else {
rson[u] = update(rson[v], idx, val, tm + 1, tr);
lson[u] = lson[v];
}
t[u] = max(t[lson[u]], t[rson[u]]);
return u;
}
4. Answering Queries-
Hopefully section 3 is clear to you. If it is, not much effort is needed here.
The first thing to do is, sort the given k nodes in order of DFS. This can be achieved by earlier done Euler Tour of tree. We can use inbuilt sort function, and use a custom comparator function which would compare two nodes on basis of their in-time. A short code to do this is below-
Click to view
sort(b.begin(), b.end(), [&](int x, int y) {
return tin[x] < tin[y];//Function used to compare two nodes. tin= in time.
});
Now, also note that how set S will be formed. Say we are given k nodes (u_1,u_2,...,u_k), and we sorted them in order to DFS. Now, the answer for any 2 adjacent query nodes, u_i and u_{i+1} is simple. We already discussed answer if there are only 2 nodes in query. The answer then was path from u to LCA(u,v) to v. Or, in other words, path from u_1 to LCA(u_1,u_2) + Path from u_2 to LCA(u2,u_{3\%2=1}). In general terms, answer for a query is path from u_i to LCA(u_i,u_{(i+1)\%N}). Few rough examples prove that this path is sufficient.
Now,look at what we have to answer. We need to find a node with value as close to r as possible. Now, val array is sorted - and we can surely use the position of value closest to r. We hence, perform a binary search on val to find the closest value of r. Now, we can transform our query to - “Query the tree the to get to leaf as close as possible corresponding to given index”.
This is done by breaking query into 2 parts. Say the index we got for the closest value was j. One part will deal from finding a index as large as possible in range [1,j-1] such that the node lies in path, and the other will deal with finding an index as small as possible in range [j,N] such that a node from that index lies on path.
I will describe the first function, and leave the other function as an exercise as both use exact same logic. We have to find the largest possible index in [1,j-1] such that a node of that index lies in S. Take a note of the necessary information, i.e. the node u whose segment tree we will be querying, and the depth[LCA(u,u_{i+1})] (we discussed use of depth[node] in above sections already).
Now, the logic goes like-
Check the interval [l,r] to which current node corresponds. The following ideas must be accommodated-
- if r\ge j try going to right child.
- if l< j and r>j then goto left child.
- if reached at leaf, return abs(t[l]-r); provided depth permits.
- At the node, do not forget to check for depth data.
- A default preference to right child is given (as we want to achieve a index as large as possible in range [1,j-1]
Hmm, looks tough? Well, I wanted it to look so! xD. In a contest you might be able to come up with these guidelines and might face problem in implementing these ideas to code.
Click to view
int prefixQuery(int v, int pos, int y, int r, int tl, int tr) {
int tm = (tl + tr) / 2;
if (tr <= pos) {//If r<=j, query right child.
if (t[v] < y) return inf;//Check depth. Diff implementations possible.
if (tl == tr) return abs(vals[tl].first - r);
if (t[rson[v]] >= y) {
return prefixQuery(rson[v], pos, y, r, tm + 1, tr);
}
return prefixQuery(lson[v], pos, y, r, tl, tm);
}
if (pos <= tm) {//Case of l<j and r>j
return prefixQuery(lson[v], pos, y, r, tl, tm);
}
int tmp = prefixQuery(rson[v], pos, y, r, tm + 1, tr);//Default preference to right child.
if (tmp != inf) return tmp;//If right child not in range given, query the left child.
return prefixQuery(lson[v], pos, y, r, tl, tm);
}
Now, you have the ideas. you know briefly how to do it for range [1,j-1]. Try working on the other function, which returns the smallest index possible in range [j,N]. The ideas are almost identical, just some changes in guidelines. Construct your guidelines, and hence realize the function. Solution for function given in tab.
Click to view
int suffixQuery(int v, int pos, int y, int r, int tl, int tr) {
int tm = (tl + tr) / 2;
if (tl >= pos) {
if (t[v] < y) return inf;
if (tl == tr) return abs(vals[tl].first - r);
if (t[lson[v]] >= y) {
return suffixQuery(lson[v], pos, y, r, tl, tm);
}
return suffixQuery(rson[v], pos, y, r, tm + 1, tr);
}
if (pos > tm) {
return suffixQuery(rson[v], pos, y, r, tm + 1, tr);
}
int tmp = suffixQuery(lson[v], pos, y, r, tl, tm);
if (tmp != inf) return tmp;
return suffixQuery(rson[v], pos, y, r, tm + 1, tr);
}
And with this, we are done with the hardest problem of the set. Please feel free to ask in case of any doubts (the things to explain were exhaustive, hence it is possible that tiny details here and there might be missed out. I’d request you to help me by pointing any such instance out. :)). Setter’s code was used as reference, and you can refer to it as well for any other needed details. 
SOLUTION:
The solution codes are also posted in tabs below for your reference incase the links dont work. Enjoy, and please help me improve the editorial by asking doubts and raising clarification requests
Click to view
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) (int)x.size()
typedef int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef vector<pii> vpii;
template<typename T>
T getint() {
T x=0,p=1;
char ch;
do{ch=getchar();}while(ch <= ' ');
if(ch=='-')p=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*p;
}
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
template<typename T1,typename T2>bool umin(T1 &x,const T2&y){if(x>y)return x=y,true;return false;}
template<typename T1,typename T2>bool umax(T1 &x,const T2&y){if(x<y)return x=y,true;return false;}
const int maxn=(int)2e5+10;
const int maxl = 18;
const int inf=(int)1e9+5;
const int mod=(int)1e9+7;
const ll llinf=(ll)1e18+5;
const ld pi=acos(-1.0);
int n, q;
int t[4 * maxn * maxl];
int lson[4 * maxn * maxl];
int rson[4 * maxn * maxl];
int depth[maxn];
vector <int> g[maxn];
int num[maxn];
int a[maxn];
vector < pair <int, int> > vals;
struct TQuery {
int y, r, pos, idx;
};
vector <TQuery> queries[maxn];
int prefixQuery(int v, int pos, int y, int r, int tl, int tr) {
int tm = (tl + tr) / 2;
if (tr <= pos) {
if (t[v] < y) return inf;
if (tl == tr) return abs(vals[tl].first - r);
if (t[rson[v]] >= y) {
return prefixQuery(rson[v], pos, y, r, tm + 1, tr);
}
return prefixQuery(lson[v], pos, y, r, tl, tm);
}
if (pos <= tm) {
return prefixQuery(lson[v], pos, y, r, tl, tm);
}
int tmp = prefixQuery(rson[v], pos, y, r, tm + 1, tr);
if (tmp != inf) return tmp;
return prefixQuery(lson[v], pos, y, r, tl, tm);
}
int suffixQuery(int v, int pos, int y, int r, int tl, int tr) {
int tm = (tl + tr) / 2;
if (tl >= pos) {
if (t[v] < y) return inf;
if (tl == tr) return abs(vals[tl].first - r);
if (t[lson[v]] >= y) {
return suffixQuery(lson[v], pos, y, r, tl, tm);
}
return suffixQuery(rson[v], pos, y, r, tm + 1, tr);
}
if (pos > tm) {
return suffixQuery(rson[v], pos, y, r, tm + 1, tr);
}
int tmp = suffixQuery(lson[v], pos, y, r, tl, tm);
if (tmp != inf) return tmp;
return suffixQuery(rson[v], pos, y, r, tm + 1, tr);
}
int query(int root, int y, int r, int pos) {
int ans = inf;
if (pos > 0) ans = min(ans, prefixQuery(root, pos - 1, y, r, 0, n - 1));
if (pos < n) ans = min(ans, suffixQuery(root, pos, y, r, 0, n - 1));
return ans;
}
int sz = 0;
int newNode() {
t[++sz] = -inf;
return sz;
}
int build(int tl, int tr, int index, int value) {
int v = newNode();
if (tl == tr) {
if (index == tl) t[v] = value;
return v;
}
int tm = (tl + tr) / 2;
lson[v] = build(tl, tm, index, value);
rson[v] = build(tm + 1, tr, index, value);
t[v] = max(t[lson[v]], t[rson[v]]);
return v;
}
int update(int v, int idx, int val, int tl, int tr) {
int u = newNode();
if (tl == tr) {
t[u] = val;
return u;
}
int tm = (tl + tr) / 2;
if (idx <= tm) {
lson[u] = update(lson[v], idx, val, tl, tm);
rson[u] = rson[v];
} else {
rson[u] = update(rson[v], idx, val, tm + 1, tr);
lson[u] = lson[v];
}
t[u] = max(t[lson[u]], t[rson[u]]);
return u;
}
int ans[maxn];
int timer;
int tin[maxn], tout[maxn];
int up[maxn][maxl];
int root[maxn];
int dfs(int v, int p) {
tin[v] = timer++;
up[v][0] = p;
for(int i = 1; i < maxl; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
if (v == 0) {
root[v] = build(0, n - 1, num[v], depth[v]);
} else {
root[v] = update(root[p], num[v], depth[v], 0, n - 1);
}
int sz = 1;
for(int x: g[v]) if (x != p) {
depth[x] = depth[v] + 1;
sz += dfs(x, v);
}
tout[v] = tin[v] + sz - 1;
return sz;
}
bool is(int x, int y) {
return tin[x] <= tin[y] && tout[y] <= tout[x];
}
int lca(int x, int y) {
if (is(x, y)) return x;
if (is(y, x)) return y;
for(int i = maxl - 1; i >= 0; --i) {
if (!is(up[x][i], y)) x = up[x][i];
}
return up[x][0];
}
void solve() {
timer = 0;
cin >> n >> q;
assert(1 <= n && n <= 100000);
assert(1 <= q && q <= 100000);
vals.clear();
for(int i = 0; i < n; ++i) {
cin >> a[i];
assert(1 <= a[i] && a[i] <= 1000000000);
g[i].clear();
queries[i].clear();
vals.push_back(make_pair(a[i], i));
}
sort(vals.begin(), vals.end());
for(int i = 0; i < n; ++i) {
num[vals[i].second] = i;
}
for(int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x; --y;
g[x].pb(y);
g[y].pb(x);
}
dfs(0, 0);
int sumK = 0;
int ans = 0;
for(int qq = 0; qq < q; ++qq) {
int r, k;
cin >> r >> k;
r ^= ans;
assert(1 <= r && r <= 1000000000);
sumK += k;
int j = upper_bound(vals.begin(), vals.end(), make_pair(r, inf)) - vals.begin();
vector <int> b(k);
for(int &x: b) {
cin >> x;
x ^= ans;
--x;
}
sort(b.begin(), b.end(), [&](int x, int y) {
return tin[x] < tin[y];
});
ans = inf;
for(int i = 0; i < k; ++i) {
int x = b[i];
int y = lca(x, b[(i + 1) % k]);
ans = min(ans, query(root[x], depth[y], r, j));
}
cout << ans << '\n';
}
}
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0);
for(int i = 0; i < maxn * 4; ++i) {
t[i] = -inf;
}
int T;
cin >> T;
assert(T <= 5);
while(T--) {
solve();
}
return 0;
}
Click to view
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
// read template
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
// end
const int X = 8 * 1e6 + 239;
const int M = 2e5 + 239;
const int N = 2 * M;
const int L = 19;
const int BIG = 1e9 + 239;
//persistent segment tree
int tree[X], ls[X], rs[X], cur;
inline int build(int i, int l, int r)
{
if (r - l == 1)
{
tree[cur] = -BIG;
ls[cur] = -1;
rs[cur] = l;
cur++;
return (cur - 1);
}
int mid = (l + r) >> 1;
int ix = cur++;
ls[ix] = build(2 * i + 1, l, mid);
rs[ix] = build(2 * i + 2, mid, r);
tree[ix] = -BIG;
return ix;
}
inline int update(int ver, int l, int r, int id, int x)
{
if (r - l == 1)
{
tree[cur] = x;
ls[cur] = -1;
rs[cur] = id;
cur++;
return (cur - 1);
}
int mid = (l + r) >> 1;
if (id < mid)
{
int ix = cur++;
ls[ix] = update(ls[ver], l, mid, id, x);
rs[ix] = rs[ver];
tree[ix] = max(tree[ls[ix]], tree[rs[ix]]);
return ix;
}
else
{
int ix = cur++;
ls[ix] = ls[ver];
rs[ix] = update(rs[ver], mid, r, id, x);
tree[ix] = max(tree[ls[ix]], tree[rs[ix]]);
return ix;
}
}
inline int gettL(int ver, int l, int r, int s, int mx)
{
if (r == s && tree[ver] < mx) return -1;
if (r - l == 1)
{
if (tree[ver] < mx) return -1;
return rs[ver];
}
int mid = (l + r) >> 1;
if (s <= mid) return gettL(ls[ver], l, mid, s, mx);
int t = gettL(rs[ver], mid, r, s, mx);
if (t != -1) return t;
return gettL(ls[ver], l, mid, mid, mx);
}
inline int gettR(int ver, int l, int r, int s, int mx)
{
if (l == s && tree[ver] < mx) return -1;
if (r - l == 1)
{
if (tree[ver] < mx) return -1;
return rs[ver];
}
int mid = (l + r) >> 1;
if (s >= mid) return gettR(rs[ver], mid, r, s, mx);
int t = gettR(ls[ver], l, mid, s, mx);
if (t != -1) return t;
return gettR(rs[ver], mid, r, mid, mx);
}
bool used[M];
int n, q, a[M], szk[M], ans, in[M], root[M], st;
vector<int> v[M];
pair<int, int> val[M];
ll sum;
inline void dfs_check(int p)
{
used[p] = true;
for (int i : v[p])
if (!used[i])
dfs_check(i);
}
int gl[N], first[N], how[N];
pair<int, int> dp[L][N];
vector<int> et;
inline void dfs_build(int p, int pr, int ver)
{
root[p] = update(ver, 0, n, in[p], gl[p]); // version of persistent segment tree in vertex p
for (int i : v[p])
if (i != pr)
dfs_build(i, p, root[p]);
}
inline void dfs_lca(int p, int pr, int f)
{
first[p] = et.size();
et.push_back(p);
gl[p] = f;
for (int i : v[p])
if (i != pr)
{
dfs_lca(i, p, f + 1);
et.push_back(p);
}
}
inline int lca(int u, int v)
{
if (first[u] > first[v]) swap(u, v);
int l = first[u];
int r = first[v];
int e = how[r - l + 1];
return min(dp[e][l], dp[e][r + 1 - (1 << e)]).second;
}
inline void init_lca()
{
et.clear();
dfs_lca(0, -1, 0);
int k = et.size();
for (int i = 0; i < k; i++) dp[0][i] = make_pair(gl[et[i]], et[i]);
for (int i = 1; i < L; i++)
for (int j = 0; j < k; j++)
{
int st = (1 << (i - 1));
if (st + j >= k)
{
dp[i][j] = dp[i - 1][j];
continue;
}
dp[i][j] = min(dp[i - 1][j], dp[i - 1][st + j]);
}
how[1] = 0;
for (int i = 2; i <= k; i++)
{
how[i] = how[i - 1];
if ((1 << (how[i] + 1)) == i) how[i]++;
}
}
inline int getans(int r, int s, int f) // get answer on way from s to f
{
int t = lower_bound(val, val + n, make_pair(r, 0)) - val; // prefix [0, t) and suffix [t, n)
int ans = BIG;
int it = -1;
if (t > 0) it = gettL(root[f], 0, n, t, gl[s]); // get nearest on prefix
if (it >= 0) ans = min(ans, abs(val[it].first - r));
it = -1;
if (t < n) it = gettR(root[f], 0, n, t, gl[s]); // get nearest on suffix
if (it >= 0) ans = min(ans, abs(val[it].first - r));
return ans;
}
inline int query(int r, vector<int> id)
{
int x = id[0];
for (int i : id) x = lca(x, i);
int ans = BIG;
for (int i : id) ans = min(ans, getans(r, x, i));
return ans;
}
inline void solve()
{
n = readIntSp(2, (int)(1e5));
q = readIntLn(2, (int)(1e5));
for (int i = 0; i < n; i++) v[i].clear();
for (int i = 0; i < n; i++)
{
if (i < n - 1)
a[i] = readIntSp(1, (int)(1e9));
else
a[i] = readIntLn(1, (int)(1e9));
}
for (int i = 0; i < n; i++)
val[i] = make_pair(a[i], i);
sort(val, val + n); // compress array a
for (int i = 0; i < n; i++)
in[val[i].second] = i;
cur = 0;
st = build(0, 0, n);
for (int i = 0; i < n - 1; i++)
{
int x = readIntSp(1, n);
int y = readIntLn(1, n);
assert(x != y);
x--, y--;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 0; i < n; i++) used[i] = false;
dfs_check(0);
for (int i = 0; i < n; i++) assert(used[i]);
init_lca();
dfs_build(0, -1, st); // build versions of persistent segment tree of all vertexes
sum = 0;
ans = 0;
for (int i = 0; i < q; i++)
{
int r = readIntSp(0, (int)(2e9));
r ^= ans;
assert(1 <= r && r <= (int)(1e9));
int k = readIntSp(1, n);
sum += k;
vector<int> id;
for (int x = 0; x < k; x++)
{
int p;
if (x < k - 1)
p = readIntSp(0, (int)(2e9));
else
p = readIntLn(0, (int)(2e9));
p ^= ans;
assert(1 <= p && p <= n);
p--;
assert(szk[p] == 0);
szk[p]++;
id.push_back(p);
}
for (int x : id) szk[x]--;
ans = query(r, id);
cout << ans << "\n";
}
assert((sum <= (ll)(3e5)));
}
int main()
{
ios::sync_with_stdio(0);
int T = readIntLn(1, 5);
sum = 0;
while (T--) solve();
assert(getchar() == -1);
return 0;
}
Time Complexity= O(Q\sum{k}(LogK +LogN)) where k is the number of nodes given in query.
CHEF VIJJU’S CORNER 
1. Here is some after thought. What if, instead of using "S is union of path from u_i to LCA(u_i,u_{(i+1)}\%N)" we use "S is union of path from u_i to LCA(u_i,u_{(i+1)}\%N) AND from u_{(i+1)\%N} to LCA(u_i,u_{(i+1)\%N})? Will any extra nodes get covered this way? Is this definition also correct, but a little inefficient? Argue.
2. Setter’s Notes-
Click to view
Suppose there is a query “R u1, u2, …, uk”.
If we sort u_1...u_k in order of dfs traversal, then the minimal set of nodes which contains u_1...u_k can be found as follows: for each i a path from u_i to lca(u_i, u_{(i+1)}) is added to the set (path u_k \implies lca(u_k, u_1) is also included).
For now, we need to answer k queries: for two given nodes a and b (a is ancestor of b) and a number R find the integer nearest to R on the path a \implies b. For doing this online, let’s do the following.
Consider that for each node v of the tree we have a segment tree with indexes made from the input values (compressed ofc). This segment tree will have the following meaning: for leaf node with index x, it contains depth of node u with value on it equal to x (or the deepest such node), with u as a node of the path from root of the tree to v. For non-leaf node of the segment tree, it’s value is computed as the maximum of it’s children nodes.
This segment tree for node v can be built from it’s parent p, just by setting value depth[v] in position value[v] in seg tree of node p, and thus is the persistence.
For answering query a b R, you need to find a position nearest to R with value in this position >= depth[a] over the segtree of node b. It can be done by two queries: one for prefix 1…R, the second one for suffix R…N. both of the them can be done in logN time, if they are implemented carefully.
3. A few practice problems-