fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(), (x).end()
  3. #define ll long long
  4. using namespace std;
  5.  
  6. static char buf[1 << 22];
  7. static int bp = 0, bl = 0;
  8. static inline int gc() {
  9.     if (bp == bl) { bl = (int)fread(buf, 1, sizeof(buf), stdin); bp = 0; if (bl == 0) return -1; }
  10.     return buf[bp++];
  11. }
  12. static inline ll rd() {
  13.     int c = gc();
  14.     while (c != -1 && (c < '0' || c > '9')) c = gc();
  15.     ll x = 0;
  16.     while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
  17.     return x;
  18. }
  19. static char obuf[1 << 22];
  20. static int op = 0;
  21. static inline void flush() { fwrite(obuf, 1, op, stdout); op = 0; }
  22. static inline void pc(char c) { if (op == (int)sizeof(obuf)) flush(); obuf[op++] = c; }
  23. static inline void wr(int x) {
  24.     if (x == 0) { pc('0'); return; }
  25.     char tmp[12]; int c = 0;
  26.     while (x > 0) { tmp[c++] = '0' + x % 10; x /= 10; }
  27.     while (c > 0) pc(tmp[--c]);
  28. }
  29.  
  30. int main() {
  31.     int t = (int)rd();
  32.     while (t--) {
  33.         int n = (int)rd(), q = (int)rd();
  34.  
  35.         vector<int> par(n + 1, 0);
  36.         vector<ll> edg(n + 1, 0);
  37.         for (int i = 2; i <= n; ++i) par[i] = (int)rd();
  38.         for (int i = 2; i <= n; ++i) edg[i] = rd();
  39.  
  40.         vector<int> deg(n + 1, 0);
  41.         for (int i = 2; i <= n; ++i) ++deg[par[i]];
  42.  
  43.         vector<int> chOff(n + 2, 0);
  44.         for (int v = 1; v <= n; ++v) chOff[v + 1] = chOff[v] + deg[v];
  45.         vector<int> chArr(max(1, n));
  46.         {
  47.             vector<int> cur(n + 2, 0);
  48.             for (int v = 1; v <= n; ++v) cur[v] = chOff[v];
  49.             for (int v = 2; v <= n; ++v) chArr[cur[par[v]]++] = v;
  50.         }
  51.  
  52.         vector<int> topo(n);
  53.         {
  54.             int h = 0, tl = 0;
  55.             topo[tl++] = 1;
  56.             while (h < tl) {
  57.                 int u = topo[h++];
  58.                 for (int i = chOff[u]; i < chOff[u + 1]; ++i) topo[tl++] = chArr[i];
  59.             }
  60.         }
  61.  
  62.         const ll MEM_LIMIT = 20000000;
  63.  
  64.         vector<ll> lcmSub(n + 1, 1);
  65.         vector<ll> totalTime(n + 1, 0);
  66.         bool canBuild = true;
  67.         ll totalMem = 0;
  68.  
  69.         for (int i = n - 1; i >= 0 && canBuild; --i) {
  70.             int u = topo[i];
  71.             if (deg[u] == 0) {
  72.                 lcmSub[u] = 1;
  73.                 totalTime[u] = 0;
  74.             } else {
  75.                 ll L = deg[u];
  76.                 for (int j = chOff[u]; j < chOff[u + 1]; ++j) {
  77.                     int c = chArr[j];
  78.                     ll g = __gcd(L, lcmSub[c]);
  79.                     ll nL = L / g * lcmSub[c];
  80.                     if (nL > MEM_LIMIT || nL < L) { canBuild = false; break; }
  81.                     L = nL;
  82.                 }
  83.                 if (!canBuild) break;
  84.                 totalMem += L;
  85.                 if (totalMem > MEM_LIMIT) { canBuild = false; break; }
  86.                 lcmSub[u] = L;
  87.             }
  88.         }
  89.  
  90.         if (canBuild) {
  91.             vector<vector<int>> tab(n + 1);
  92.             for (int i = n - 1; i >= 0; --i) {
  93.                 int u = topo[i];
  94.                 if (deg[u] == 0) {
  95.                     tab[u].assign(1, u);
  96.                 } else {
  97.                     ll L = lcmSub[u];
  98.                     tab[u].resize((size_t)L);
  99.                     int d = deg[u];
  100.                     for (ll r = 0; r < L; ++r) {
  101.                         int idx = (int)(r % (ll)d);
  102.                         int c = chArr[chOff[u] + idx];
  103.                         ll nr = (r + (ll)edg[c]) % lcmSub[c];
  104.                         tab[u][(size_t)r] = tab[c][(size_t)nr];
  105.                     }
  106.                 }
  107.                 for (int j = chOff[u]; j < chOff[u + 1]; ++j) {
  108.                     vector<int>().swap(tab[chArr[j]]);
  109.                 }
  110.             }
  111.  
  112.             ll L1 = lcmSub[1];
  113.             vector<int>& root = tab[1];
  114.             for (int i = 0; i < q; ++i) {
  115.                 ll m = rd();
  116.                 wr(root[(size_t)(m % L1)]);
  117.                 pc((i + 1 == q) ? '\n' : ' ');
  118.             }
  119.         } else {
  120.             vector<int> jmp(n + 1);
  121.             vector<ll> addT(n + 1, 0);
  122.             for (int i = n - 1; i >= 0; --i) {
  123.                 int u = topo[i];
  124.                 if (deg[u] == 1) {
  125.                     int c = chArr[chOff[u]];
  126.                     jmp[u] = jmp[c];
  127.                     addT[u] = edg[c] + addT[c];
  128.                 } else {
  129.                     jmp[u] = u;
  130.                     addT[u] = 0;
  131.                 }
  132.             }
  133.             int startU = jmp[1];
  134.             ll startAdd = addT[1];
  135.             for (int i = 0; i < q; ++i) {
  136.                 ll m = rd();
  137.                 int u = startU;
  138.                 ll T = m + startAdd;
  139.                 while (deg[u] != 0) {
  140.                     int d = deg[u];
  141.                     int idx = (int)(T % (ll)d);
  142.                     int c = chArr[chOff[u] + idx];
  143.                     T += edg[c] + addT[c];
  144.                     u = jmp[c];
  145.                 }
  146.                 wr(u);
  147.                 pc((i + 1 == q) ? '\n' : ' ');
  148.             }
  149.         }
  150.     }
  151.  
  152.     flush();
  153.     return 0;
  154. }
  155.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
3 1
1 1
10 20
4
10 5
1 2 2 2 1 1 3 4 5
1 2 3 4 5 6 7 8 9
1 2 3 4 5
stdout
copy 
2
6 7 9 6 7
https://ideone.com/fC7td5
language:
C++ (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!