毕业设计做APP好还是网站,中装建设千股千评,在线教育,小程序导航网站开发好吧#xff0c;洛谷的数据比较水暴力就可以过。。。。#xff08;而且跑到飞快#xff09; 不过#xff08;BZ水不过去#xff09;还是讲讲正规的做法。 其实一眼可以看出可以树剖#xff0c;但是#xff0c;码起来有点麻烦。 其实有一种更简单的离线做法。 我们很容易… 好吧洛谷的数据比较水暴力就可以过。。。。而且跑到飞快 不过BZ水不过去还是讲讲正规的做法。 其实一眼可以看出可以树剖但是码起来有点麻烦。 其实有一种更简单的离线做法。 我们很容易联想到并查集利用并查集来维护各个点的最近的标记的祖先但是加入标记后会产生分离的操作这对并查集来说不好操作 所以我们先将所有的询问读入将所有的标记都打上去。 从后往前处理。如果有一个点的标记变为了0就将该点与它的父亲合并。 不知为何在luogu上跑的比暴力要慢一点。。。。 # includeiostream
# includecstdio
# includecmath
# includecstring
# includealgorithm
using namespace std;
const int mn 100005;
int n,m;
int c[mn],a[mn],fa[mn],ans[mn];
char opt[mn];
struct edge{int next,to;}e[mn*2];
int head[mn],edge_max;
inline void add_edge(int x,int y)
{e[edge_max](edge){head[x],y};head[x]edge_max;
}
int f[mn];//并查集的fa数组
int find(int x)
{return f[x]x?x:f[x]find(f[x]);
}
void dfs(int x)
{f[x]c[x]?x:fa[x];for(int ihead[x];i;ie[i].next){int ye[i].to;if (y!fa[x]) fa[y]x,dfs(y);}
}
int main()
{int x,y;scanf(%d%d,n,m);for(int i1;in;i){scanf(%d%d,x,y);add_edge(x,y);add_edge(y,x);}c[1]1;for(int i1;im;i){scanf( %c%d,opt[i],a[i]);if (opt[i]C) c[a[i]];}dfs(1);for(int im;i1;i--){if (opt[i]C){c[a[i]]--;if(!c[a[i]])f[a[i]]fa[a[i]];}else ans[i]find(a[i]);}for(int i1;im;i){if(ans[i])printf(%d\n,ans[i]);}return 0;
}转载于:https://www.cnblogs.com/logeadd/p/8685974.html
