regex0754

TATAKAI

Jun 11th, 2021 (edited)
94
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "bits/stdc++.h"
  2. #include "ext/pb_ds/assoc_container.hpp"
  3. #include "ext/pb_ds/tree_policy.hpp"
  4. using namespace std;
  5.  
  6. #pragma GCC optimize("O3","unroll-loops")
  7. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  8. #pragma GCC target("avx2")
  9.  
  10. #define sync ios_base::sync_with_stdio(0); cin.tie(0);
  11. #define all(x) x.begin(),x.end()
  12. #define unq(a) sort(all(a));a.resize(unique(all(a)) - a.begin())
  13. #define ll long long
  14. #define ld long double
  15. #define pb push_back
  16. #define fi first
  17. #define se second
  18. #define endl '\n'
  19. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  20. //mt19937 rng(7);
  21. using pii = pair<int , int>;
  22.  
  23. int inline max(const int x, const int y){return (x > y ? x : y);}
  24. int inline min(const int x, const int y){return (x < y ? x : y);}
  25.  
  26. const int base = 31;
  27. const int mxn = 1e5 + 5, mod0 = 1e9 + 7, mod1 = 1e9 + 9;
  28. vector<pii> g[mxn];
  29. bitset<mxn> blocked;
  30. int sz[mxn];
  31. vector<int> dg[mxn];
  32.  
  33. int n, q;
  34. const int LOG = 17;
  35. int dep[mxn], par[LOG][mxn], ch[mxn];
  36. int h0[mxn], ih0[mxn], h1[mxn], ih1[mxn], tw0[mxn], itw0[mxn], tw1[mxn], itw1[mxn];
  37.  
  38. void pre(){
  39. for (int i = 1;i < LOG;i++){
  40. for (int j = 1;j <= n;j++){
  41. par[i][j] = par[i - 1][par[i - 1][j]];
  42. }
  43. }
  44. }
  45.  
  46. int inline jump(int x, int d){
  47. for (int i = 0; i < LOG;i++){
  48. if (d & (1 << i)){
  49. x = par[i][x];
  50. }
  51. }
  52. return x;
  53. }
  54.  
  55. int inline lca(int u, int v){
  56. if (dep[u] < dep[v]) swap(u , v);
  57. u = jump(u , dep[u] - dep[v]);
  58. if (u == v) return u;
  59. for (int i = LOG - 1;i >= 0;i--){
  60. if (par[i][u] == par[i][v]) continue;
  61. u = par[i][u]; v = par[i][v];
  62. }
  63. return par[0][u];
  64. }
  65.  
  66. void dfs0(int cur, int p, ll l){
  67. h0[cur] = (h0[p] + tw0[l] * 1ll * ch[cur]) % mod0;
  68. ih0[cur] = (ih0[p] + itw0[l] * 1ll * ch[cur]) % mod0;
  69.  
  70. h1[cur] = (h1[p] + tw1[l] * 1ll * ch[cur]) % mod1;
  71. ih1[cur] = (ih1[p] + itw1[l] * 1ll * ch[cur]) % mod1;
  72.  
  73. dep[cur] = l;
  74. par[0][cur] = p;
  75. for (const pair<int , int>& x : g[cur]){
  76. if (x.fi == p) continue;
  77. dfs0(x.fi, cur, l + x.se);
  78. }
  79. }
  80.  
  81. int inline power(ll x, ll y, ll md = mod0){
  82. ll r = 1;
  83. while(y > 0){
  84. if (y & 1){
  85. r = (r * x) % md;
  86. }
  87. y >>= 1;
  88. x = (x * x) % md;
  89. }
  90. return r;
  91. }
  92.  
  93.  
  94. int root;
  95. int get_centroid(int cur, int p){
  96. int mx = sz[root] - sz[cur], to = -1;
  97. for (const pii& nxt : g[cur]){
  98. int x = nxt.fi;
  99. if (blocked[x] or x == p) continue;
  100. if (sz[x] > mx){
  101. mx = sz[x];
  102. to = x;
  103. }
  104. }
  105. if (mx <= sz[root] / 2){
  106. return cur;
  107. }
  108. return get_centroid(to , cur);
  109. }
  110. int plink[mxn];
  111.  
  112. void dfs(int cur, int p){
  113. sz[cur] = 1;
  114. for (const pii& nxt : g[cur]){
  115. int x = nxt.fi;
  116. if (blocked[x] or x == p) continue;
  117. dfs(x, cur);
  118. sz[cur] += sz[x];
  119. }
  120. }
  121.  
  122. int decompose(int cur){
  123. dfs(cur , 0);
  124. root = cur;
  125. int centroid = get_centroid(cur , 0);
  126. blocked[centroid] = 1;
  127.  
  128. for (const pii& nxt : g[centroid]){
  129. int x = nxt.fi;
  130. if (blocked[x]) continue;
  131. dg[centroid].push_back(decompose(x));
  132. plink[dg[centroid].back()] = centroid;
  133. }
  134. return centroid;
  135. }
  136.  
  137. int inline get_dis(int x, int y){
  138. return dep[x] + dep[y] - 2 * dep[lca(x , y)];
  139. }
  140.  
  141. struct Query{
  142. int id, u, d;
  143. Query(){}
  144. Query(int _x, int _y, int _z){
  145. id = _x;
  146. u = _y;
  147. d = _z;
  148. }
  149. };
  150.  
  151. struct Path_hash{
  152. bool inv;
  153. int u, v, lc, x, hsh0, hsh1, hingdis;
  154. Path_hash(pii p){
  155. u = p.fi; v = p.se; lc = lca(u , v);
  156. inv = (dep[u] > dep[lc] ? 0 : 1);
  157. hingdis = dep[u] - dep[lc] + 1;
  158. }
  159. pii get(int d){
  160. if (inv){
  161. int s = par[0][u];
  162. d = (dep[v] - dep[u] + 1) - d;
  163. x = jump(v , d);
  164. hsh0 = ((h0[x] - h0[s]) * 1ll * itw0[dep[u]]) % mod0;
  165. hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
  166. hsh1 = ((h1[x] - h1[s]) * 1ll * itw1[dep[u]]) % mod1;
  167. hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
  168. }
  169. else{
  170. if (d <= hingdis){
  171. x = jump(u , d);
  172. hsh0 = (ih0[u] * 1ll * tw0[dep[u]]) % mod0 - (ih0[x] * 1ll * tw0[d + dep[x]]) % mod0;
  173. hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
  174. hsh1 = (ih1[u] * 1ll * tw1[dep[u]]) % mod1 - (ih1[x] * 1ll * tw1[d + dep[x]]) % mod1;
  175. hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
  176. }
  177. else{
  178. int dd = hingdis;
  179. x = par[0][lc];
  180. hsh0 = (ih0[u] * 1ll * tw0[dep[u]]) % mod0 - (ih0[x] * 1ll * tw0[dd + dep[x]]) % mod0;
  181. hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
  182. hsh1 = (ih1[u] * 1ll * tw1[dep[u]]) % mod1 - (ih1[x] * 1ll * tw1[dd + dep[x]]) % mod1;
  183. hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
  184.  
  185. d -= dd;
  186. dd = dep[v] - dep[lc];
  187. d = dd - d;
  188. assert(d >= 0);
  189. x = jump(v , d);
  190. hsh0 += ((h0[x] - h0[lc]) * 1ll * (hingdis > dep[lc] ? tw0[hingdis - dep[lc] - 1] : itw0[dep[lc] + 1 - hingdis])) % mod0;
  191. hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
  192. hsh1 += ((h1[x] - h1[lc]) * 1ll * (hingdis > dep[lc] ? tw1[hingdis - dep[lc] - 1] : itw1[dep[lc] + 1 - hingdis])) % mod1;
  193. hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
  194. }
  195. }
  196. return {hsh0, hsh1};
  197. }
  198. int inline encode(){
  199. return get(get_dis(u , v) + 1).fi;
  200. }
  201. };
  202.  
  203. struct Path{
  204. int start, end, lc;
  205. Path() : start(0), end(0), lc(0) {}
  206. Path(int s, int e){
  207. start = s;
  208. end = e;
  209. lc = lca(s , e);
  210. }
  211.  
  212. int inline at(int d){
  213. int u = start, v = end;
  214. if (dep[u] > dep[lc]){
  215. if (d <= dep[u] - dep[lc] + 1){
  216. return jump(u , d - 1);
  217. }
  218. else{
  219. d -= (dep[u] - dep[lc] + 1);
  220. d = dep[v] - dep[lc] - d;
  221. return jump(v , d);
  222. }
  223. }
  224. else{
  225. d = dep[v] - dep[u] + 1 - d;
  226. return jump(v , d);
  227. }
  228. }
  229.  
  230. Path LexLess(Path& p0, Path& p1){
  231. Path_hash h0(pii{p0.start , p0.end}), h1(pii{p1.start , p1.end});
  232. int lo, hi, md, ix = -1;
  233. lo = 1; hi = min(get_dis(p0.start , p0.end) , get_dis(p1.start , p1.end)) + 1;
  234. while(lo <= hi){
  235. md = (lo + hi) / 2;
  236. if (h0.get(md) != h1.get(md)){
  237. ix = md;
  238. hi = md - 1;
  239. }
  240. else{
  241. lo = md + 1;
  242. }
  243. }
  244. if (~ix) return (ch[p0.at(ix)] < ch[p1.at(ix)] ? p0 : p1);
  245. return (get_dis(p0.start , p0.end) < get_dis(p1.start , p1.end) ? p0 : p1);
  246. }
  247. };
  248.  
  249. vector<Query> Q[mxn];
  250. vector<Query> qe[mxn];
  251. bitset<mxn> bt;
  252. Path s[mxn];
  253. vector<pair<Path , Path>> ans_candidates[mxn];
  254.  
  255. void AddQ(int id, int u, int d){
  256. int cur = u;
  257. while(cur){
  258. int nd = get_dis(u, cur) + 1;
  259. if (d >= nd){
  260. Q[cur].push_back(Query(id, u, d));
  261. }
  262. cur = plink[cur];
  263. }
  264. }
  265.  
  266. void mdfs(int cur, int p, int l, vector<pair<int , Path>>& dt){
  267. int curd = get_dis(root , cur) + 1;
  268. dt.push_back({curd, Path(root , cur)});
  269. Path prf(cur , root);
  270. for (const Query& q : qe[cur]){
  271. int d = q.d - curd + 1;
  272. if (bt[d]){
  273. ans_candidates[q.id].push_back({prf , s[d]});
  274. }
  275. }
  276. for (const int& x : dg[cur]){
  277. if (cur == p) continue;
  278. mdfs(x, cur, l + 1, dt);
  279. }
  280. }
  281.  
  282. void Solve(int R){
  283. if (!Q[R].size()) return;
  284. vector<Query>& q = Q[R];
  285. root = R;
  286.  
  287. for (const Query& w : q){
  288. qe[w.u].push_back(w);
  289. }
  290.  
  291. bt[1] = 1;
  292. s[1] = Path(R , R);
  293.  
  294. vector<int> idx;
  295. vector<pair<int , Path>> subdt;
  296. for (const int& c : dg[R]){
  297. subdt.clear();
  298. mdfs(c, R, 1, subdt);
  299. for (pair<int , Path>& dt : subdt){
  300. if (bt[dt.fi]) s[dt.fi] = s[dt.fi].LexLess(s[dt.fi] , dt.se);
  301. else s[dt.fi] = dt.se, bt[dt.fi] = 1, idx.push_back(dt.fi);
  302. }
  303. }
  304.  
  305. for (const Query& q : qe[R]){
  306. int d = q.d;
  307. if (bt[d]){
  308. ans_candidates[q.id].push_back({Path(R , R) , s[d]});
  309. }
  310. }
  311.  
  312. for (const int& x : idx) bt[x] = 0;
  313. reverse(all(dg[R]));
  314.  
  315. idx.clear();
  316. for (const int& c : dg[R]){
  317. subdt.clear();
  318. mdfs(c, R, 1, subdt);
  319. for (pair<int , Path>& dt : subdt){
  320. if (bt[dt.fi]) s[dt.fi] = s[dt.fi].LexLess(s[dt.fi] , dt.se);
  321. else s[dt.fi] = dt.se, bt[dt.fi] = 1, idx.push_back(dt.fi);
  322. }
  323. }
  324.  
  325. for (const Query& q : qe[R]){
  326. int d = q.d;
  327. if (bt[d]){
  328. ans_candidates[q.id].push_back({Path(R , R) , s[d]});
  329. }
  330. }
  331.  
  332. for (const int& x : idx) bt[x] = 0;
  333. bt[1] = 0;
  334. for (const Query& w : q){
  335. qe[w.u].clear();
  336. }
  337. }
  338.  
  339. int main(){
  340.  
  341. #ifndef ONLINE_JUDGE
  342. freopen("input.txt", "r", stdin);
  343. freopen("output.txt", "w", stdout);
  344. #endif
  345.  
  346. sync
  347.  
  348. int t = 1;
  349. scanf("%d", &t);
  350.  
  351. int a = power(base , mod0 - 2, mod0), b = power(base, mod1 - 2, mod1);
  352. tw0[0] = tw1[0] = itw0[0] = itw1[0] = 1;
  353. for (int i = 1; i < mxn; i++){
  354. tw0[i] = (tw0[i - 1] * 1ll * base) % mod0;
  355. tw1[i] = (tw1[i - 1] * 1ll * base) % mod1;
  356.  
  357. itw0[i] = (itw0[i - 1] * 1ll * a) % mod0;
  358. itw1[i] = (itw1[i - 1] * 1ll * b) % mod1;
  359. }
  360.  
  361. while(t--){
  362. scanf("%d%d", &n, &q);
  363. char c;
  364. for (int i = 1; i <= n; i++){
  365. scanf(" %c", &c);
  366. ch[i] = (c - 'a') + 1;
  367. }
  368.  
  369. for (int u, v, w, i = 0; i < n - 1; i++){
  370. scanf("%d%d", &u, &v);
  371. w = 1;
  372. g[u].push_back({v, w});
  373. g[v].push_back({u, w});
  374. }
  375.  
  376. dfs0(1, 0, 1);
  377. pre();
  378. decompose(1);
  379.  
  380. for (int u, d, i = 0; i < q; i++){
  381. scanf("%d%d", &u, &d);
  382. AddQ(i, u, d);
  383. }
  384.  
  385. for (int i = 1; i <= n; i++) Solve(i);
  386. for (int i = 0; i < q; i++){
  387. if (ans_candidates[i].size()){
  388. Path res(ans_candidates[i][0].fi.start , ans_candidates[i][0].se.end), tmp;
  389. for (int j = 1; j < ans_candidates[i].size(); j++){
  390. tmp = Path(ans_candidates[i][j].fi.start , ans_candidates[i][j].se.end);
  391. res = res.LexLess(res , tmp);
  392. }
  393. cout << Path_hash({res.start , res.end}).encode() << endl;
  394. }
  395. else{
  396. cout << -1 << endl;
  397. }
  398. }
  399. for (int i = 0; i <= n; i++) g[i].clear(), dg[i].clear(), Q[i].clear(), blocked[i] = 0, plink[i] = 0;
  400. for (int i = 0; i <= q; i++) ans_candidates[i].clear();
  401. }
  402. cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s ";
  403. return 0;
  404. }
RAW Paste Data