用ps做美食网站,做外贸网站需要注意些什么手续,电商如何推广自己的产品,网站的元素有哪些正题 题目大意
一棵树#xff0c;开始全是白点#xff0c;两个操作
将一个节点翻转询问一颗棋子与所有面朝上为黑色的棋子lca最深的那个的编号 解题思路
必备技能#xff1a;平衡树#xff08;或set库的使用方法#xff09;#xff0c;大量卡常技巧#xff0c;LCA
我…正题 题目大意
一棵树开始全是白点两个操作
将一个节点翻转询问一颗棋子与所有面朝上为黑色的棋子lca最深的那个的编号 解题思路
必备技能平衡树或set库的使用方法大量卡常技巧LCA
我们可以发现和一个点的lca最深的话这个点一定是在dfs序上最近的点这时候我们就要使用平衡树了。 每多一个黑点就将dfs序加入平衡树删除就去掉。然后询问一个点的时候就在平衡树上查询离他dfs最近的一个黑点然后求LCA。 这里就不敲平衡树了反正set也行
不过直接用dfs会爆炸所以要用奇特的方法计算dfs序。 code
注意以下代码包含大量卡常操作如果对您的眼睛造成了伤害那我表示道歉。
#pragma GCC optimize(O2)
#includecstdio
#includealgorithm
#includeset
#includecmath
#includequeue
#includecctype
#define N 800010
using namespace std;
struct line{int to,next,w;
}a[N];
int tot,n,m,x,y,ls[N],dep[N],t,cnt,T,que[N];
int dfn[N],put[N],f[N][24],dis[N][24],siz[N];
setint s;
queueint q;
__attribute__((optimize(O3))) inline int read() {int x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
__attribute__((optimize(O3))) inline void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
__attribute__((optimize(O3))) void dfs()//求dfs序
{int h0,t1;que[h]1;dfn[1]1; put[dfn[1]]1;while(ht) {int xque[h],lastx;for(register int ils[x];i;ia[i].next){int ya[i].to;dfn[y]dfn[last](last!x?siz[last]:1);put[dfn[y]]y;que[t]y;lasty;}}
}
__attribute__((optimize(O3))) void bfs(int s)//预处理LCA
{int h0,t1;que[h]1;while(ht) {int xque[h];siz[x]1;for(register int ils[x];i;ia[i].next) {int ya[i].to;dep[y]dep[x]1,f[y][0]x;que[t]y;}}for(register int in;i1;i--)siz[f[que[i]][0]]siz[que[i]];T(int)(log(n)/log(2))1;for (int j1;jT;j){for (int i1;in;i){f[i][j]f[f[i][j-1]][j-1];dis[i][j]min(dis[i][j-1],dis[f[i][j-1]][j-1]);}}cnt0;
}
__attribute__((optimize(O3))) int LCA(int x,int y)//求LCA
{if (dep[x]dep[y]) swap(x,y);for (int iT;i0;i--)if (dep[f[y][i]]dep[x]) yf[y][i];if (xy) return x;for (int iT;i0;i--)if (f[y][i]!f[x][i]) {xf[x][i];yf[y][i];}return f[x][0];
}
__attribute__((optimize(O3))) void print(int x){if (x9) print(x/10); putchar(x%1048); return;
}
__attribute__((optimize(O3))) signed main()
{nread();mread();for(register int i2;in;i){addl(read(),i);}bfs(1);dfs();dep[0]-1;for(register int i1;im;i){xread();if(x0){if(!s.insert(dfn[x]).second) s.erase(dfn[x]);//加点or去点}else{xabs(x);int t10,t20;setint::iterator ys.lower_bound(dfn[x]);if(y!s.end()) t1LCA(x,put[*y]);if(y!s.begin()) y--,t2LCA(x,put[*y]);if(dep[t1]dep[t2]) print(t2),putchar(\n);else print(t1),putchar(\n);}//求最近的}
}
