Guest User

Untitled

a guest
May 3rd, 2020
200
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #ifdef LOCAL
  6.     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  7. #else
  8.     #define eprintf(...) 42
  9. #endif
  10.  
  11. using ll = long long;
  12. using ld = long double;
  13. using uint = unsigned int;
  14. template<typename T>
  15. using pair2 = pair<T, T>;
  16. using pii = pair<int, int>;
  17. using pli = pair<ll, int>;
  18. using pll = pair<ll, ll>;
  19. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  20.  
  21. #define pb push_back
  22. #define mp make_pair
  23. #define all(x) (x).begin(),(x).end()
  24. #define fi first
  25. #define se second
  26.  
  27. const int maxn = 300005;
  28. const int MAGIC = 200; //0;
  29.  
  30. vector<int> ids[maxn];
  31. vector<int> f[maxn];
  32. int tin[maxn], tout[maxn];
  33. int d[maxn];
  34. int typ[maxn], node[maxn], mod[maxn], rem[maxn], add[maxn];
  35. vector<int> gr[maxn];
  36. int answer[maxn];
  37. int timer;
  38. int n, nq;
  39. int pos[maxn];
  40.  
  41. inline void addF(vector<int> &f, int x, int t)
  42. {
  43.     for (; x < (int)f.size(); x |= (x + 1))
  44.     {
  45.         f[x] += t;
  46.     }
  47. }
  48.  
  49. inline int getF(vector<int> &f, int x)
  50. {
  51.     int ans = 0;
  52.     for (; x >= 0; x = (x & (x + 1)) - 1)
  53.     {
  54.         ans += f[x];
  55.     }
  56.     return ans;
  57. }
  58.  
  59. void go(int cur, int curd = 0)
  60. {
  61.     tin[cur] = timer++;
  62.     d[tin[cur]] = curd;
  63.     ids[curd].pb(tin[cur]);
  64.     for (auto t : gr[cur]) go(t, curd + 1);
  65.     tout[tin[cur]] = timer - 1;
  66. }
  67.  
  68. void solve()
  69. {
  70.     scanf("%d%d", &n, &nq);
  71.     for (int i = 0; i < n; i++) gr[i].clear();
  72.     for (int i = 1; i < n; i++)
  73.     {
  74.         int x;
  75.         scanf("%d", &x);
  76.         x--;
  77.         gr[x].pb(i);
  78.     }
  79.     timer = 0;
  80.     for (int i = 0; i < n; i++) ids[i].clear();
  81.     go(0);
  82.     for (int i = 0; i < n; i++)
  83.     {
  84.         f[i].clear();
  85.         f[i].resize(ids[i].size());
  86.     }
  87.    
  88.     for (int q = 0; q < nq; q++)
  89.     {
  90.         scanf("%d", &typ[q]);
  91.         if (typ[q] == 2)
  92.         {
  93.             int a;
  94.             scanf("%d", &a);
  95.             a--;
  96.             a = tin[a];
  97.             node[q] = a;
  98.         } else
  99.         {
  100.             int a;
  101.             scanf("%d%d%d%d", &a, &mod[q], &rem[q], &add[q]);
  102.             a--;
  103.             a = tin[a];
  104.             node[q] = a;
  105.         }
  106.     }
  107.    
  108.     for (int q = 0; q < nq; q++)
  109.     {
  110.         if (typ[q] == 2)
  111.         {
  112.             int a = node[q];
  113.             int curd = d[a];
  114.             int wh = lower_bound(all(ids[curd]), a) - ids[curd].begin();
  115.             answer[q] = getF(f[curd], wh);
  116.         } else if (mod[q] > MAGIC)
  117.         {
  118.             int a = node[q];
  119.             int l = a;
  120.             int r = tout[a];
  121.             int curd = d[a] + rem[q];
  122.             while (curd < n)
  123.             {
  124.                 int ll = lower_bound(all(ids[curd]), l) - ids[curd].begin();
  125.                 int rr = upper_bound(all(ids[curd]), r) - ids[curd].begin();
  126.                 if (rr == ll) break;
  127.                 addF(f[curd], ll, add[q]);
  128.                 addF(f[curd], rr, -add[q]);
  129.                 curd += mod[q];
  130.             }
  131.         }
  132.     }
  133.     cerr << clock() << endl;
  134.     for (int md = 1; md <= MAGIC; md++)
  135.     {
  136.         for (int i = 0; i < md; i++) ids[i].clear();
  137.         for (int i = 0; i < n; i++)
  138.         {
  139.             int curd = d[i] % md;
  140.             pos[i] = (int)ids[curd].size();
  141.             ids[curd].pb(i);
  142.         }
  143.         for (int i = 0; i < md; i++)
  144.         {
  145.             f[i].clear();
  146.             f[i].resize((int)ids[i].size());
  147.         }
  148.         for (int q = 0; q < nq; q++)
  149.         {
  150.             if (typ[q] == 2)
  151.             {
  152.                 int a = node[q];
  153.                 int curd = d[a] % md;
  154.                 int wh = pos[a];
  155.                 answer[q] += getF(f[curd], wh);
  156.             } else if (mod[q] == md)
  157.             {
  158.                 int a = node[q];
  159.                 int l = a;
  160.                 int r = tout[a];
  161.                 int curd = (d[a] + rem[q]) % md;
  162.                 int ll = lower_bound(all(ids[curd]), l) - ids[curd].begin();
  163.                 int rr = upper_bound(all(ids[curd]), r) - ids[curd].begin();
  164.                 if (rr != ll)
  165.                 {
  166.                     addF(f[curd], ll, add[q]);
  167.                     addF(f[curd], rr, -add[q]);
  168.                 }
  169.             }
  170.         }
  171.     }
  172.    
  173.     for (int q = 0; q < nq; q++) if (typ[q] == 2) printf("%d\n", answer[q]);
  174. }
  175.  
  176. int main()
  177. {
  178.     int NT;
  179.     scanf("%d", &NT);
  180.     for (int T = 0; T < NT; T++)
  181.     {
  182.         solve();
  183.     }
  184.     return 0;
  185. }
RAW Paste Data