如题

在ABC202三天后用树上莫队 $n\sqrt{n}$ 过了E题 (2e5 @ 158ms) 之后有感而发

或者随便编个数据把我的代码卡掉吧 顺便看看我的代码还有哪里很糟糕 谢谢了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define int long long
#define inlint inline int
#define inloid inline void
#define EDGE(cu) for(int ed = nodes[cu].lastConn, to = edges[ed].to; ed; ed = edges[ed].next, to = edges[ed].to)
#define MAXN 200005
using namespace std;

namespace _MAIN{
	int n, m;
	inlint read(){
		register char c = getchar();
		int nega = 1, num = 0;
		for(;!isdigit(c);c = getchar()) if(c == '-') nega = -1;
		for(; isdigit(c);c = getchar()) num = num * 10 + c - '0';
		return nega * num;
	}
} using namespace _MAIN;

namespace _TREE{
	struct node{
		int lastConn, dep, F, heaLink, heaChild, siz, next, st, en;
	} nodes[MAXN];
	int euler[2 * MAXN], euCnt;
	struct edge{
		int next, to;
	} edges[2 * MAXN];
	int edCnt;
	void dfs1(int cu){
		nodes[cu].dep = nodes[nodes[cu].F].dep + 1;
		nodes[cu].siz = 1;
		euler[++euCnt] = cu;
		nodes[cu].st = euCnt;		
		EDGE(cu){
			if(to != nodes[cu].F){
				nodes[to].F = cu;
				dfs1(to);
				nodes[cu].siz += nodes[to].siz;
				if(nodes[to].siz > nodes[nodes[cu].heaChild].siz) nodes[cu].heaChild = to;
			}
		}
		euler[++euCnt] = cu;
		nodes[cu].en = euCnt;		
	}
	void dfs2(int cu, int ro){
		nodes[cu].heaLink = ro;
		if(nodes[cu].heaChild) dfs2(nodes[cu].heaChild, ro);
		EDGE(cu){
			if(to ^ nodes[cu].heaChild && to ^ nodes[cu].F) dfs2(to, to);
		}
	}
	inloid addEdge(int a, int b){
		edges[++edCnt].next = nodes[a].lastConn, edges[edCnt].to = b, nodes[a].lastConn = edCnt;
		edges[++edCnt].next = nodes[b].lastConn, edges[edCnt].to = a, nodes[b].lastConn = edCnt;
	}
	inlint LCA(int a, int b){
		while(nodes[a].heaLink != nodes[b].heaLink){
			if(nodes[nodes[a].heaLink].dep < nodes[nodes[b].heaLink].dep) swap(a, b);
			a = nodes[nodes[a].heaLink].F;
		}
		return nodes[a].dep > nodes[b].dep ? b : a;
	}	
} using namespace _TREE;

namespace _MO{
	int blockInd[2 * MAXN], sq;
	struct que{
		int l, r, id, dep, gotLCA;
		bool operator < (const que &b){
			return blockInd[l] ^ blockInd[b.l] ? l < b.l : blockInd[l] & 1 ? r < b.r : r > b.r;
		}
	} queries[MAXN];
	int cnt[MAXN], l = 1, r, ans[MAXN], euCnt[MAXN];
	inloid add(int x){
		++cnt[nodes[x].dep - 1]; 
	}
	inloid sub(int x){
		--cnt[nodes[x].dep - 1];
	}
	inloid edit(int x){
		(euCnt[x] ^= 1) ? add(x) : sub(x);
	}
	inloid solv(int num){
		while(l > queries[num].l) add(euler[--l]);
		while(r < queries[num].r) add(euler[++r]);
		while(l < queries[num].l) sub(euler[l++]);
		while(r > queries[num].r) sub(euler[r--]);
		ans[queries[num].id] = cnt[queries[num].dep] >> 1;
	}
	void init(){
        if(m) sq = n * 2 / sqrt(m * 2 / 3) + 1;
        for(int i = 1;i <= 2 * n;i++){
            blockInd[i] = i / sq + 1;
        }
        sort(queries + 1, queries + 1 + m);
    }
} using namespace _MO;

signed main(void){
	n = read();
	for(int i = 2; i <= n; i++){
		addEdge(i, read());
	}
	dfs1(1);
	dfs2(1, 1);
	m = read();
	for(int i = 1;i <= m;i++){
		int p = read();
		queries[i].l = nodes[p].st, queries[i].r = nodes[p].en, queries[i].dep = read(), queries[i].id = i;
	}
	init();
	for(int i = 1;i <= m;i++){
		solv(i);
	}
	for(int i = 1;i <= m;i++){
		cout << ans[i] << "\n";
	}
}