大意：

给出一颗以1为根的树，一开始每个节点都是一颗棋子，一面白一面黑，白色的面朝上

接下来就q次操作，操作分两种

0操作 将一个颗棋子翻转

1操作 询问一颗棋子与所有面朝上为黑色的棋子lca最深的那个的编号

解题思路：

LCA(最近公共祖先) + DFS序

不早了先不发详细题解

开氧气才能过，能优化的都优化了，还是T，75分，开了就A了

看：

Accepted code：

#pragma GCC optimize(2) #include
    
     #include
     
      #include
      
       #define rgi register int#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2?EOF:*p1++)using namespace std;const int N = 800010;int n, q, tot, cnt;int dfn[N], id[N], f[N][24], dep[N], next[N], to[N], last[N], siz[N], que[N];set 
       
         S;set 
        
         ::iterator it;char buf[1 << 21], *p1, *p2;inline int in() {
     	int f = 0, flag = 1; char c = getchar();	while(!isdigit(c)) {
     if(c == '-') flag = -1; c = getchar();}	while(isdigit(c)) f = (f << 3) + (f << 1) + c - 48, c = getchar();	return f * flag;}int LCA(int x,int y) {
     	if(dep[x] < dep[y]) swap(x, y);	rgi need = dep[x] - dep[y];	for(rgi i = 0; need; need >>= 1, ++i) if(need & 1) x = f[x][i];	if(x != y) {
     		for (rgi i = 21; i >= 0; i--) if(f[x][i] != f[y][i]) 			x = f[x][i], y = f[y][i];		return f[x][0];	}	return x;}void bfs_() {
         rgi h = 0, t = 1, u, v;    que[++h] = 1;    while(h <= t) {
             u = que[h++];        siz[u] = 1;        for (rgi i = last[u]; i; i = next[i]) {
                 v = to[i];            dep[v] = dep[u]+1, f[v][0] = u;            que[++t] = v;        }    }    for (rgi i = n; i >= 1; i--) siz[f[que[i]][0]]+=siz[que[i]];}void bfs__() {
         rgi h = 0, t = 1, u, v, Last;    que[++h] = dfn[1] = id[1] = 1;    while(h <= t) {
             u = que[h++], Last = u;        for (rgi i = last[u]; i; i = next[i]) {
                 v = to[i];            dfn[v] = dfn[Last] + (Last !=u ? siz[Last] : 1);            id[dfn[v]] = v;            que[++t] = v;            Last = v;        }    }}void Init() {
     	n = in(), q = in();	rgi fa;	for (rgi i = 2; i <= n; ++i)		{
      fa = in(), to[++cnt] = i, next[cnt] = last[fa], last[fa] = cnt; }	bfs_(), bfs__(); dep[0] = -1;	for (rgi j = 1; (1 << j) <= n; ++j)		for (rgi i = 1; i <= n; ++i)			if (f[i][j - 1]) f[i][j] = f[f[i][j - 1]][j - 1];}void print(int x) {
     	if (x > 9) print(x / 10); putchar(x % 10 + 48); return;}void Main() {
     	rgi flag, t, T, F;	for (rgi i = 1; i <= q; ++i) {
     		flag = in(), F = 0;		if (flag < 0) F = 1, flag = -flag;		if (!F) {
     			if (!S.insert(dfn[flag]).second)				S.erase(dfn[flag]);			continue;		}		if (S.empty()) {
      putchar(48), putchar('\n'); continue;}		t = 0, T = 0;		it = S.lower_bound(dfn[flag]);		if (it != S.end()) t = LCA(flag, id[*it]);		if (it != S.begin()) it--, T = LCA(flag, id[* it]);		print(dep[t] < dep[T] ? T : t); putchar('\n');	}}int main() {
     	/*freopen("watch.in","r",stdin);	freopen("watch.out","w",stdout);*/	Init();	Main();	return 0;}