View difference between Paste ID: w1pNXYZM and 6igqX0s8

 #include <bits/stdc++.h>
 
 using namespace std;
 
 #ifdef LOCAL
     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
 #else
     #define eprintf(...) 42
 #endif
 
 using ll = long long;
 using ld = long double;
 using uint = unsigned int;
 template<typename T>
 using pair2 = pair<T, T>;
 using pii = pair<int, int>;
 using pli = pair<ll, int>;
 using pll = pair<ll, ll>;
 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 #define pb push_back
 #define mp make_pair
 #define all(x) (x).begin(),(x).end()
 #define fi first
 #define se second
 
 const int maxn = 300005;
 const int MAGIC = 200; //0;
 
 vector<int> ids[maxn];
 vector<int> f[maxn];
 int tin[maxn], tout[maxn];
 int d[maxn];
 int typ[maxn], node[maxn], mod[maxn], rem[maxn], add[maxn];
 vector<int> gr[maxn];
 int answer[maxn];
 int timer;
 int n, nq;
 int pos[maxn];
 
 inline void addF(vector<int> &f, int x, int t)
 {
 	for (; x < (int)f.size(); x |= (x + 1))
 	{
 		f[x] += t;
 	}
 }
 
 inline int getF(vector<int> &f, int x)
 {
 	int ans = 0;
 	for (; x >= 0; x = (x & (x + 1)) - 1)
 	{
 		ans += f[x];
 	}
 	return ans;
 }
 
 void go(int cur, int curd = 0)
 {
 	tin[cur] = timer++;
 	d[tin[cur]] = curd;
 	ids[curd].pb(tin[cur]);
 	for (auto t : gr[cur]) go(t, curd + 1);
 	tout[tin[cur]] = timer - 1;
 }
 
 void solve()
 {
 	scanf("%d%d", &n, &nq);
 	for (int i = 0; i < n; i++) gr[i].clear();
 	for (int i = 1; i < n; i++)
 	{
 		int x;
 		scanf("%d", &x);
 		x--;
 		gr[x].pb(i);
 	}
 	timer = 0;
 	for (int i = 0; i < n; i++) ids[i].clear();
 	go(0);
 	for (int i = 0; i < n; i++)
 	{
 		f[i].clear();
 		f[i].resize(ids[i].size());
 	}
 
 	for (int q = 0; q < nq; q++)
 	{
 		scanf("%d", &typ[q]);
 		if (typ[q] == 2)
 		{
 			int a;
 			scanf("%d", &a);
 			a--;
 			a = tin[a];
 			node[q] = a;
 		} else
 		{
 			int a;
 			scanf("%d%d%d%d", &a, &mod[q], &rem[q], &add[q]);
 			a--;
 			a = tin[a];
 			node[q] = a;
 		}
 	}
 
 	for (int q = 0; q < nq; q++)
 	{
 		if (typ[q] == 2)
 		{
 			int a = node[q];
 			int curd = d[a];
 			int wh = lower_bound(all(ids[curd]), a) - ids[curd].begin();
 			answer[q] = getF(f[curd], wh);
 		} else if (mod[q] > MAGIC)
 		{
 			int a = node[q];
 			int l = a;
 			int r = tout[a];
 			int curd = d[a] + rem[q];
 			while (curd < n)
 			{
 				int ll = lower_bound(all(ids[curd]), l) - ids[curd].begin();
 				int rr = upper_bound(all(ids[curd]), r) - ids[curd].begin();
 				if (rr == ll) break;
 				addF(f[curd], ll, add[q]);
 				addF(f[curd], rr, -add[q]);
 				curd += mod[q];
 			}
 		}
 	}
 	cerr << clock() << endl;
 	for (int md = 1; md <= MAGIC; md++)
 	{
 		for (int i = 0; i < md; i++) ids[i].clear();
 		for (int i = 0; i < n; i++)
 		{
 			int curd = d[i] % md;
 			pos[i] = (int)ids[curd].size();
 			ids[curd].pb(i);
 		}
 		for (int i = 0; i < md; i++)
 		{
 			f[i].clear();
 			f[i].resize((int)ids[i].size());
 		}
 		for (int q = 0; q < nq; q++)
 		{
 			if (typ[q] == 2)
 			{
 				int a = node[q];
 				int curd = d[a] % md;
 				int wh = pos[a];
 				answer[q] += getF(f[curd], wh);
 			} else if (mod[q] == md)
 			{
 				int a = node[q];
 				int l = a;
 				int r = tout[a];
 				int curd = (d[a] + rem[q]) % md;
 				int ll = lower_bound(all(ids[curd]), l) - ids[curd].begin();
 				int rr = upper_bound(all(ids[curd]), r) - ids[curd].begin();
 				if (rr != ll)
 				{
 					addF(f[curd], ll, add[q]);
 					addF(f[curd], rr, -add[q]);
 				}
 			}
 		}
 	}
 
 	for (int q = 0; q < nq; q++) if (typ[q] == 2) printf("%d\n", answer[q]);
 }
 
 int main()
 {
 	int NT;
 	scanf("%d", &NT);
 	for (int T = 0; T < NT; T++)
 	{
 		solve();
 	}
     return 0;
 }