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, lim = 1e3, 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.    i128 x, y;
  55.    i128 gcd = extended_euclid(a.fi, b.fi, x, y);
  56.    if((b.se - a.se) % gcd)
  57.       return {-1, -1};
  58.    i128 lcm = a.fi / gcd * b.fi;
  59.    i128 ans = (x * (b.se - a.se) / gcd * a.fi + a.se) % lcm;
  60.    if(ans < 0) ans += lcm;
  61.    if(ans > 1e18) return {-1, -1};
  62.    return {lcm, ans};
  63. }
  64.  
  65. struct leaves {
  66.    i128 m, r;
  67.    int id;
  68. };
  69.  
  70. vector<pii> graph[maxn];
  71. vector<int> ct[maxn];
  72. pair<i128, i128> req[maxn];
  73. int par[maxn] = {}, ss[maxn], del[maxn], is_leaf[maxn];
  74. ll path[maxn];
  75.  
  76. void dfs(int u, int p, pair<i128, i128> cur, ll sum = 0) {
  77.    if(cur.fi == -1) return;
  78.    path[u] = sum;
  79.    req[u] = cur;
  80.  
  81.    int cnt = 0;
  82.    for(pii v : graph[u])
  83.       if(v.fi != p) {
  84.          int mod = int(graph[u].size()) - (u != 1);
  85.          pii nxt = {mod, (cnt++ - sum) % mod};
  86.          if(nxt.se < 0) nxt.se += mod;
  87.          pair<i128, i128> burb = crt(cur, nxt);
  88.  
  89.          dfs(v.fi, u, burb, sum + v.se);
  90.       }
  91. }
  92.  
  93.  
  94. void compute_size(int u, int p) {
  95.    ss[u] = 1;
  96.    for(auto[v, w] : graph[u])
  97.       if(v != p && !del[v])
  98.          compute_size(v, u), ss[u] += ss[v];
  99. }
  100.  
  101. int find_centroid(int u, int p, int n) {
  102.    for(auto[v, w] : graph[u])
  103.       if(v != p && !del[v] && ss[v] > n / 2)
  104.          return find_centroid(v, u, n);
  105.    return u;
  106. }
  107.  
  108. int init(int u) {
  109.    compute_size(u, 0);
  110.    u = find_centroid(u, 0, ss[u]);
  111.    del[u] = 1;
  112.    for(auto[v, w] : graph[u])
  113.       if(!del[v] && v != par[u])
  114.          ct[u].pb(init(v));
  115.       else if(v != par[u]) ct[u].pb(0);
  116.    if(!del[par[u]] && u != 1) par[u] = init(par[u]);
  117.    return u;
  118. }
  119.  
  120. bool check(ll x, pair<i128, i128> p) {
  121.    return x % p.fi == p.se;
  122. }
  123.  
  124. int vis[maxn] = {};
  125.  
  126. int special_binary_search(ll x, int root) {
  127.    vector<int> order;
  128.    int ans = root;
  129.    while(!(is_leaf[ans])) {
  130. //      assert(!vis[ans]);
  131. //      if(!ans) cout << order.back() << endl;
  132.       vis[ans] = 1;
  133.       order.pb(ans);
  134. //      assert(ans);
  135.       if(check(x, req[ans]))
  136.          ans = ct[ans][(path[ans] + x) % (int(ct[ans].size()))];
  137.       else ans = par[ans];
  138.    }
  139.    for(int e : order)
  140.       vis[e] = 0;
  141.    return ans;
  142. }
  143.  
  144. void solve() {
  145.    int n, m; cin >> n >> m;
  146.    foru(i, 1, n) graph[i].clear(), ct[i].clear(), req[i] = {-1, -1}, del[i] = 0;
  147.  
  148.    vector<pii> edges(n + 1);
  149.    foru(i, 2, n) cin >> edges[i].fi, par[i] = edges[i].fi;
  150.    foru(i, 2, n) cin >> edges[i].se;
  151.    foru(i, 2, n) graph[edges[i].fi].pb({i, edges[i].se}),
  152.                  graph[i].pb({edges[i].fi, edges[i].se});
  153.    foru(i, 2, n)
  154.       is_leaf[i] = (graph[i].size() == 1), sort(all(graph[i]));
  155.  
  156.    dfs(1, 0, {1, 0});
  157.    int root = init(1);
  158.  
  159.    vector<int> ans;
  160.    while(m--) {
  161.       ll x; cin >> x;
  162.       if(n == 1)
  163.          ans.pb(1);
  164.       else ans.pb(special_binary_search(x, root));
  165.    }
  166.    for(int a : ans)
  167.       cout << a << ' ';
  168.    cout << endl;
  169. }
  170.  
  171. int main() {
  172.    ios_base::sync_with_stdio(0); cin.tie(0);
  173.    file(name, ".out");
  174.    //file and ios boost
  175.  
  176.    int t; cin >> t;
  177.    while(t--)
  178.       solve();
  179. }
  180.  
Runtime error #stdin #stdout 0.02s 37112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OYXng2
used binary searching-like on centroid
language:
C++ (gcc 8.3)
created:
3 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!