# TATAKAI - Editorial

We will solve all the queries offline. The topics which we will require are centroid decomposition, rolling hash, lca and binary lifting. Lets say we have a node u and there is some query whose starting node is u. Then we can check all the paths(In given tree) whose one end is u using the ancestors of u in centroid tree(These ancestors will be internal nodes of paths in given tree). This can be done by maintaining an array for each path_length (Of paths in given tree) from current root (current root is root of subtree while traversing a subtree of decomposed tree) which will have least lexicographic “path” and we do updates everytime we go to a node.

After each update we need least lexicographic answer possible. So for update, we use binary search on hashes (which we can store in O(N) and query them in O(1) time) and binary lifting to find the first node / character between two candidate “path” to get the first mismatch and we compare them accordingly.

The final time complexity is O((N+Q)∗log^3N) in which O(N∗logN) is from travelling each subtree of centroid tree, O(Q∗logN) is from getting the final path for each query. Also, every time we perform an update it takes O(log^2N)(Because of my implementation).

If any one has other approach / solution then do mention them here.

Solution :

``````#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2")

#define sync ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
#define unq(a) sort(all(a));a.resize(unique(all(a)) - a.begin())
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define endl '\n'
//mt19937 rng(7);
using pii = pair<int , int>;

int inline max(const int x, const int y){return (x > y ? x : y);}
int inline min(const int x, const int y){return (x < y ? x : y);}

const int base = 31;
const int mxn = 1e5 + 5, mod0 = 1e9 + 7, mod1 = 1e9 + 9;
vector<pii> g[mxn];
bitset<mxn> blocked;
int sz[mxn];
vector<int> dg[mxn];

int n, q;
const int LOG = 17;
int dep[mxn], par[LOG][mxn], ch[mxn];
int h0[mxn], ih0[mxn], h1[mxn], ih1[mxn], tw0[mxn], itw0[mxn], tw1[mxn], itw1[mxn];

void pre(){
for (int i = 1;i < LOG;i++){
for (int j = 1;j <= n;j++){
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
}

int inline jump(int x, int d){
for (int i = 0; i < LOG;i++){
if (d & (1 << i)){
x = par[i][x];
}
}
return x;
}

int inline lca(int u, int v){
if (dep[u] < dep[v]) swap(u , v);
u = jump(u , dep[u] - dep[v]);
if (u == v) return u;
for (int i = LOG - 1;i >= 0;i--){
if (par[i][u] == par[i][v]) continue;
u = par[i][u]; v = par[i][v];
}
return par[0][u];
}

void dfs0(int cur, int p, ll l){
h0[cur] = (h0[p] + tw0[l] * 1ll * ch[cur]) % mod0;
ih0[cur] = (ih0[p] + itw0[l] * 1ll * ch[cur]) % mod0;

h1[cur] = (h1[p] + tw1[l] * 1ll * ch[cur]) % mod1;
ih1[cur] = (ih1[p] + itw1[l] * 1ll * ch[cur]) % mod1;

dep[cur] = l;
par[0][cur] = p;
for (const pair<int , int>& x : g[cur]){
if (x.fi == p) continue;
dfs0(x.fi, cur, l + x.se);
}
}

int inline power(ll x, ll y, ll md = mod0){
ll r = 1;
while(y > 0){
if (y & 1){
r = (r * x) % md;
}
y >>= 1;
x = (x * x) % md;
}
return r;
}

int root;
int get_centroid(int cur, int p){
int mx = sz[root] - sz[cur], to = -1;
for (const pii& nxt : g[cur]){
int x = nxt.fi;
if (blocked[x] or x == p) continue;
if (sz[x] > mx){
mx = sz[x];
to = x;
}
}
if (mx <= sz[root] / 2){
return cur;
}
return get_centroid(to , cur);
}

void dfs(int cur, int p){
sz[cur] = 1;
for (const pii& nxt : g[cur]){
int x = nxt.fi;
if (blocked[x] or x == p) continue;
dfs(x, cur);
sz[cur] += sz[x];
}
}

int decompose(int cur){
dfs(cur , 0);
root = cur;
int centroid = get_centroid(cur , 0);
blocked[centroid] = 1;

for (const pii& nxt : g[centroid]){
int x = nxt.fi;
if (blocked[x]) continue;
dg[centroid].push_back(decompose(x));
}
return centroid;
}

int inline get_dis(int x, int y){
return dep[x] + dep[y] - 2 * dep[lca(x , y)];
}

struct Query{
int id, u, d;
Query(){}
Query(int _x, int _y, int _z){
id = _x;
u = _y;
d = _z;
}
};

struct Path_hash{
bool inv;
int u, v, lc, x, hsh0, hsh1, hingdis;
Path_hash(pii p){
u = p.fi; v = p.se; lc = lca(u , v);
inv = (dep[u] > dep[lc] ? 0 : 1);
hingdis = dep[u] - dep[lc] + 1;
}
pii get(int d){
if (inv){
int s = par[0][u];
d = (dep[v] - dep[u] + 1) - d;
x = jump(v , d);
hsh0 = ((h0[x] - h0[s]) * 1ll * itw0[dep[u]]) % mod0;
hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
hsh1 = ((h1[x] - h1[s]) * 1ll * itw1[dep[u]]) % mod1;
hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
}
else{
if (d <= hingdis){
x = jump(u , d);
hsh0 = (ih0[u] * 1ll * tw0[dep[u]]) % mod0 - (ih0[x] * 1ll * tw0[d + dep[x]]) % mod0;
hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
hsh1 = (ih1[u] * 1ll * tw1[dep[u]]) % mod1 - (ih1[x] * 1ll * tw1[d + dep[x]]) % mod1;
hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
}
else{
int dd = hingdis;
x = par[0][lc];
hsh0 = (ih0[u] * 1ll * tw0[dep[u]]) % mod0 - (ih0[x] * 1ll * tw0[dd + dep[x]]) % mod0;
hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
hsh1 = (ih1[u] * 1ll * tw1[dep[u]]) % mod1 - (ih1[x] * 1ll * tw1[dd + dep[x]]) % mod1;
hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;

d -= dd;
dd = dep[v] - dep[lc];
d = dd - d;
assert(d >= 0);
x = jump(v , d);
hsh0 += ((h0[x] - h0[lc]) * 1ll * (hingdis > dep[lc] ? tw0[hingdis - dep[lc] - 1] : itw0[dep[lc] + 1 - hingdis])) % mod0;
hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
hsh1 += ((h1[x] - h1[lc]) * 1ll * (hingdis > dep[lc] ? tw1[hingdis - dep[lc] - 1] : itw1[dep[lc] + 1 - hingdis])) % mod1;
hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
}
}
return {hsh0, hsh1};
}
int inline encode(){
return get(get_dis(u , v) + 1).fi;
}
};

struct Path{
int start, end, lc;
Path() : start(0), end(0), lc(0) {}
Path(int s, int e){
start = s;
end = e;
lc = lca(s , e);
}

int inline at(int d){
int u = start, v = end;
if (dep[u] > dep[lc]){
if (d <= dep[u] - dep[lc] + 1){
return jump(u , d - 1);
}
else{
d -= (dep[u] - dep[lc] + 1);
d = dep[v] - dep[lc] - d;
return jump(v , d);
}
}
else{
d = dep[v] - dep[u] + 1 - d;
return jump(v , d);
}
}

Path LexLess(Path& p0, Path& p1){
Path_hash h0(pii{p0.start , p0.end}), h1(pii{p1.start , p1.end});
int lo, hi, md, ix = -1;
lo = 1; hi = min(get_dis(p0.start , p0.end) , get_dis(p1.start , p1.end)) + 1;
while(lo <= hi){
md = (lo + hi) / 2;
if (h0.get(md) != h1.get(md)){
ix = md;
hi = md - 1;
}
else{
lo = md + 1;
}
}
if (~ix) return (ch[p0.at(ix)] < ch[p1.at(ix)] ? p0 : p1);
return (get_dis(p0.start , p0.end) < get_dis(p1.start , p1.end) ? p0 : p1);
}
};

vector<Query> Q[mxn];
vector<Query> qe[mxn];
bitset<mxn> bt;
Path s[mxn];
vector<pair<Path , Path>> ans_candidates[mxn];

void AddQ(int id, int u, int d){
int cur = u;
while(cur){
int nd = get_dis(u, cur) + 1;
if (d >= nd){
Q[cur].push_back(Query(id, u, d));
}
}
}

void mdfs(int cur, int p, int l, vector<pair<int , Path>>& dt){
int curd = get_dis(root , cur) + 1;
dt.push_back({curd, Path(root , cur)});
Path prf(cur , root);
for (const Query& q : qe[cur]){
int d = q.d - curd + 1;
if (bt[d]){
ans_candidates[q.id].push_back({prf , s[d]});
}
}
for (const int& x : dg[cur]){
if (cur == p) continue;
mdfs(x, cur, l + 1, dt);
}
}

void Solve(int R){
if (!Q[R].size()) return;
vector<Query>& q = Q[R];
root = R;

for (const Query& w : q){
qe[w.u].push_back(w);
}

bt[1] = 1;
s[1] = Path(R , R);

vector<int> idx;
vector<pair<int , Path>> subdt;
for (const int& c : dg[R]){
subdt.clear();
mdfs(c, R, 1, subdt);
for (pair<int , Path>& dt : subdt){
if (bt[dt.fi]) s[dt.fi] = s[dt.fi].LexLess(s[dt.fi] , dt.se);
else s[dt.fi] = dt.se, bt[dt.fi] = 1, idx.push_back(dt.fi);
}
}

for (const Query& q : qe[R]){
int d = q.d;
if (bt[d]){
ans_candidates[q.id].push_back({Path(R , R) , s[d]});
}
}

for (const int& x : idx) bt[x] = 0;
reverse(all(dg[R]));

idx.clear();
for (const int& c : dg[R]){
subdt.clear();
mdfs(c, R, 1, subdt);
for (pair<int , Path>& dt : subdt){
if (bt[dt.fi]) s[dt.fi] = s[dt.fi].LexLess(s[dt.fi] , dt.se);
else s[dt.fi] = dt.se, bt[dt.fi] = 1, idx.push_back(dt.fi);
}
}

for (const Query& q : qe[R]){
int d = q.d;
if (bt[d]){
ans_candidates[q.id].push_back({Path(R , R) , s[d]});
}
}

for (const int& x : idx) bt[x] = 0;
bt[1] = 0;
for (const Query& w : q){
qe[w.u].clear();
}
}

int main(){

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

sync

int t = 1;
scanf("%d", &t);

int a = power(base , mod0 - 2, mod0), b = power(base, mod1 - 2, mod1);
tw0[0] = tw1[0] = itw0[0] = itw1[0] = 1;
for (int i = 1; i < mxn; i++){
tw0[i] = (tw0[i - 1] * 1ll * base) % mod0;
tw1[i] = (tw1[i - 1] * 1ll * base) % mod1;

itw0[i] = (itw0[i - 1] * 1ll * a) % mod0;
itw1[i] = (itw1[i - 1] * 1ll * b) % mod1;
}

while(t--){
scanf("%d%d", &n, &q);
char c;
for (int i = 1; i <= n; i++){
scanf(" %c", &c);
ch[i] = (c - 'a') + 1;
}

for (int u, v, w, i = 0; i < n - 1; i++){
scanf("%d%d", &u, &v);
w = 1;
g[u].push_back({v, w});
g[v].push_back({u, w});
}

dfs0(1, 0, 1);
pre();
decompose(1);

for (int u, d, i = 0; i < q; i++){
scanf("%d%d", &u, &d);
}

for (int i = 1; i <= n; i++) Solve(i);
for (int i = 0; i < q; i++){
if (ans_candidates[i].size()){
Path res(ans_candidates[i][0].fi.start , ans_candidates[i][0].se.end), tmp;
for (int j = 1; j < ans_candidates[i].size(); j++){
tmp = Path(ans_candidates[i][j].fi.start , ans_candidates[i][j].se.end);
res = res.LexLess(res , tmp);
}
cout << Path_hash({res.start , res.end}).encode() << endl;
}
else{
cout << -1 << endl;
}
}
for (int i = 0; i <= n; i++) g[i].clear(), dg[i].clear(), Q[i].clear(), blocked[i] = 0, plink[i] = 0;
for (int i = 0; i <= q; i++) ans_candidates[i].clear();
}
cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s    ";
return 0;
}
``````