fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define str string
  5. #define endl '\n'
  6. #define pb push_back
  7. #define Mask(i, j) (i & (1 << j))
  8. #define fi first
  9. #define se second
  10. #define all(a) a.begin(), a.end()
  11. #define foru(c, a, b)  for(ite_type c = a; c <= b; ++c)
  12. #define ford(c, a, b)  for(ite_type c = a; c >= b; --c)
  13. #define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  14. #define file(x, sur) if(fopen((x + ".inp").c_str(), "r")) \
  15.                         freopen((x + ".inp").c_str(), "r", stdin), \
  16.                         freopen((x + sur).c_str(), "w", stdout);
  17.  
  18. using namespace std;
  19.  
  20. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. ll Rand(ll l, ll r) {
  23.     return l + rd() % (r - l + 1);
  24. }
  25.  
  26. const str name = "not_yet_defined";
  27. typedef int ite_type;
  28. typedef __int128 i128;
  29. typedef pair<int, int> pii;
  30.  
  31. const bool is_file = 0, is_making_ans = 0;
  32. const int ntest = 200;
  33. const int maxn = 5e5 + 9, max_ai = 1e4;
  34. const ll inf = 1e18, int_inf = 0x3f3f3f3f;
  35. const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2},
  36.           dy[] = {1, -1, 2, -2, 2, -2, 1, -1};
  37. const int mod = 998244353;
  38.  
  39. i128 extended_euclid(__int128 a, __int128 b, __int128& x, __int128& y) {
  40.    if(!b) {
  41.       x = 1, y = 0;
  42.       return a;
  43.    }
  44.    i128 tmp = extended_euclid(b, a % b, x, y);
  45.    i128 c = x;
  46.    x = y;
  47.    y = c - (a / b) * y;
  48.    return tmp;
  49. }
  50.  
  51. pair<i128, i128> crt(pair<i128, i128> a, pair<i128, i128> b) {
  52.    if(a.fi < b.fi) swap(a, b);
  53.    if(b.fi == 1) return a;
  54.    if(a.fi > inf)
  55.       if(a.se % b.fi == b.se) return a;
  56.       else return {-1, -1};
  57.    i128 x, y;
  58.    i128 gcd = extended_euclid(a.fi, b.fi, x, y);
  59.    if((b.se - a.se) % gcd)
  60.       return {-1, -1};
  61.    i128 lcm = a.fi / gcd * b.fi;
  62.    i128 ans = (x % (b.fi / gcd) * (b.se - a.se) / gcd % (b.fi / gcd) * a.fi + a.se) % lcm;
  63.    if(ans < 0) ans += lcm;
  64.    if(ans > 1e18) return {-1, -1};
  65.    return {lcm, ans};
  66. }
  67.  
  68. struct leaves {
  69.    i128 m, r;
  70.    int id;
  71. };
  72.  
  73. vector<pii> graph[maxn];
  74. vector<int> ct[maxn];
  75. pair<i128, i128> req[maxn];
  76. int par[maxn] = {}, ss[maxn], del[maxn], is_leaf[maxn];
  77. ll path[maxn];
  78.  
  79. void dfs(int u, int p, pair<i128, i128> cur, ll sum = 0) {
  80.    if(cur.fi == -1) return;
  81.    path[u] = sum;
  82.    req[u] = cur;
  83.  
  84.    int cnt = 0;
  85.    for(pii v : graph[u])
  86.       if(v.fi != p) {
  87.          int mod = int(graph[u].size()) - (u != 1);
  88.          pii nxt = {mod, (cnt++ - sum) % mod};
  89.          if(nxt.se < 0) nxt.se += mod;
  90.          pair<i128, i128> burb = crt(cur, nxt);
  91.  
  92.          dfs(v.fi, u, burb, sum + v.se);
  93.       }
  94. }
  95.  
  96.  
  97. void compute_size(int u, int p) {
  98.    ss[u] = 1;
  99.    for(auto[v, w] : graph[u])
  100.       if(v != p && !del[v])
  101.          compute_size(v, u), ss[u] += ss[v];
  102. }
  103.  
  104. int find_centroid(int u, int p, int n) {
  105.    for(auto[v, w] : graph[u])
  106.       if(v != p && !del[v] && ss[v] > n / 2)
  107.          return find_centroid(v, u, n);
  108.    return u;
  109. }
  110.  
  111. int init(int u) {
  112.    compute_size(u, 0);
  113.    u = find_centroid(u, 0, ss[u]);
  114.    del[u] = 1;
  115.    for(auto[v, w] : graph[u])
  116.       if(!del[v] && v != par[u])
  117.          ct[u].pb(init(v));
  118.       else if(v != par[u]) ct[u].pb(0);
  119.    if(!del[par[u]] && u != 1) par[u] = init(par[u]);
  120.    return u;
  121. }
  122.  
  123. bool check(ll x, pair<i128, i128> p) {
  124.    return x % p.fi == p.se;
  125. }
  126.  
  127. int vis[maxn] = {};
  128.  
  129. int special_binary_search(ll x, int root) {
  130.    int ans = root;
  131.    while(!(is_leaf[ans]))
  132.       if(check(x, req[ans]))
  133.          ans = ct[ans][(path[ans] + x) % (int(ct[ans].size()))], assert(ans);
  134.       else ans = par[ans];
  135.    return ans;
  136. }
  137.  
  138. void solve() {
  139.    int n, m; cin >> n >> m;
  140.    foru(i, 1, n) graph[i].clear(), ct[i].clear(), req[i] = {-1, -1}, del[i] = 0;
  141.  
  142.    vector<pii> edges(n + 1);
  143.    foru(i, 2, n) cin >> edges[i].fi, par[i] = edges[i].fi;
  144.    foru(i, 2, n) cin >> edges[i].se;
  145.    foru(i, 2, n) graph[edges[i].fi].pb({i, edges[i].se}),
  146.                  graph[i].pb({edges[i].fi, edges[i].se});
  147.    foru(i, 2, n)
  148.       is_leaf[i] = (graph[i].size() == 1), sort(all(graph[i]));
  149.  
  150.    dfs(1, 0, {1, 0});
  151.    int root = init(1);
  152.  
  153.    while(m--) {
  154.       ll x; cin >> x;
  155.       if(n == 1)
  156.          cout << 1 << ' ';
  157.       else cout << special_binary_search(x, root) << ' ';
  158.    }
  159.    cout << endl;
  160. }
  161.  
  162. int main() {
  163.    ios_base::sync_with_stdio(0); cin.tie(0);
  164.    file(name, ".out");
  165.    //file and ios boost
  166.  
  167.    int t; cin >> t;
  168.    while(t--)
  169.       solve();
  170. }
  171.  
Runtime error #stdin #stdout 0.02s 36456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YacS7r
language:
C++ (gcc 8.3)
created:
10 days 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!