你问为什么赛时排行榜上找不到我？因为我知道自己啥都不会交就是爆零所以就没交……
但是我真的有认真地思考了好久……caorong为证！
判词有云：霁月难逢，彩云易散，心比天高，身在B层
B. 选择
当时的想法是是跑个tarjan，判断两个点缩点之后有没有在同一组，至于删边操作，就把每个边都存一下，预处理出每次询问时边的状态，对每一个询问把边清空重建再重新tarjan一下……到考试结束连样例都没调出来……
考试结束后跑到网上搜题解结果全是LCT，于是就咕了……啊如果我现在有时间的话好想去学个LCT啊
看到您的题解时感觉眼前的世界都变得辽阔%%%Chen_jr
//两点之间路径全被标记过可以用并查集维护，而并到一个集合上之后树的具体形态已经不重要了
//每次把路径上遍历的点的父亲都改成lca，在并查集中合并即可
//——我不明白的是为什么要更改树上的父亲，而不是直接在并查集中合并
//Re：大概是为了给以后求LCA节省时间，因为合并的目标是相同的 //全都清空，所以前面的操作不影响答案
//比如提前把问题里的树边加上什么的
//如果是非树边，就把u到v路径上的边(点)染色
//S1...==0代表两个点在树上连通，其实S2应该也可以做到这个？
//S2连接时用到的树是全体时间的树，所以其中lca的出现时间可能不合法
//那为什么还能往上合并啊AAA———把删边看成加边的话，时间最晚的时候边最少
//u或v和lca之间的树边可能不存在
//如果这两个点在树上的路径本来就不存在……
//不对——和lca之间有断边的话，因为这是一棵树，所以u和v在S1上就不可能连通
//lca是从u到v的必经点嘛
//也不用担心重新循环一遍树的形态会变，顺序相同，u和v都是排好序的，
//就是重新建树应该也是一样的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int N = 1e7 + 2;
const int mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, q;
char c[3];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct edge
{
int u, v;
edge(){}
edge(int x, int y)
{
//u = min(u, v);
//v = max(u, v);
u = min(x, y);
v = max(x, y);
}
friend bool operator < (const edge x, const edge y)
{
return x.u == y.u ? x.v < y.v : x.u < y.u;
}
};
set<edge> s;
struct Edge
{
int next, to;
}a[maxn<<1];
int head[maxn], len = 1;
void add(int x, int y)
{
a[++len].to = y; a[len].next = head[x];
head[x] = len;
}
struct opt
{
int op, u, v, ans;
}o[maxn];
struct SET
{
int f[maxn];
void pre(int x)
{
for(int i=1; i<=x; i++) f[i] = i;
}
int fa(int x)
{
return f[x] = f[x] == x ? x : fa(f[x]);
}
bool hb(int x, int y)
{
x = fa(x), y = fa(y);
if(x != y) f[x] = y;
else return false;
return true;
}
}S1, S2;
void link(int u, int v)
{
if(S1.hb(u, v) == 0) return;
add(u, v); add(v, u);
}
int dep[maxn], fa[maxn];
void dfs(int x)//搞得还真是个树了
{
for(int i=head[x]; i; i=a[i].next)
{
int v = a[i].to;
if(dep[v]) continue;
dep[v] = dep[x] + 1;
fa[v] = x;
dfs(v);
}
}
int LCA(int u, int v)//所以这是个朴素算法！？
{
while(fa[u] != fa[v])
{
if(dep[fa[u]] > dep[fa[v]]) u = fa[u];
else v = fa[v];
}
return u == v ? u : fa[u];
}
//两点之间路径全被标记过可以用并查集维护，而并到一个集合上之后树的具体形态已经不重要了
//每次把路径上遍历的点的父亲都改成lca，在并查集中合并即可
//——我不明白的是为什么要更改树上的父亲，而不是直接在并查集中合并
//Re：大概是为了给以后求LCA节省时间，因为合并的目标是相同的
void modify(int u, int v)
{
int lca = LCA(u, v);
if(lca == 0) return;
while(u != lca && u)
{
S2.hb(u, lca);
int lx = u;
u = fa[u];
fa[lx] = lca;
}
u = v;
while(u != lca && u)
{
S2.hb(u, lca);
int lx = u;
u = fa[u];
fa[lx] = lca;
}
}
int main()
{
n = read(); m = read(); q = read();
for(int i=1; i<=m; i++)
{
int u = read(), v = read();
s.insert(edge(u, v));
}
for(int i=1; i<=q; i++)
{
scanf("%s", c); o[i].u = read(); o[i].v = read();
if(c[0] == 'Z') o[i].op = 1, s.erase(edge(o[i].u, o[i].v));
else o[i].op = 0;
}
S1.pre(n);
for(auto x : s) link(x.u, x.v);//先建一个生成树，有可能是森林
for(int i=q; i>=1; i--)
{
if(o[i].op) link(o[i].u, o[i].v);//生成树继续完善但还是一棵树（森林）
}
for(int i=1; i<=n; i++)
{
if(!dep[i]) dep[i] = 1, dfs(i);
}
S1.pre(n); S2.pre(n);
//全都清空，所以前面的操作不影响答案
//比如提前把问题里的树边加上什么的
//如果是非树边，就把u到v路径上的边(点)染色
//S1...==0代表两个点在树上连通，其实S2应该也可以做到这个？
//S2连接时用到的树是全体时间的树，所以其中lca的出现时间可能不合法
//那为什么还能往上合并啊AAA———把删边看成加边的话，时间最晚的时候边最少
//u或v和lca之间的树边可能不存在
//如果这两个点在树上的路径本来就不存在……
//不对——和lca之间有断边的话，因为这是一棵树，所以u和v在S1上就不可能连通
//lca是从u到v的必经点嘛
//也不用担心重新循环一遍树的形态会变，顺序相同，u和v都是排好序的，
//就是重新建树应该也是一样的
for(auto x : s)
{
if(S1.hb(x.u, x.v) == 0) modify(x.u, x.v);
}
for(int i=q; i>=1; i--)
{
if(o[i].op)
{
if(S1.hb(o[i].u, o[i].v)) continue;
modify(o[i].u, o[i].v);
}
else o[i].ans = S2.fa(o[i].u) == S2.fa(o[i].v) ? 1 : 0;
}
for(int i=1; i<=q; i++)
{
if(!o[i].op)
{
if(o[i].ans) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
View Code
标签：ch,并查,int,S2,fa,开坑,lca,邀请赛 From： https://www.cnblogs.com/Catherine2006/p/16585806.html