hdu 6200 mustedge mustedge(并查集+树状数组 或者 LCT 缩点)

hdu 6200 mustedge mustedge(并查集+树状数组 或者 LCT 缩点)

题意:

给一张无向连通图,有两种操作

1 u v 加一条边(u,v)

2 u v 计算u到v路径上桥的个数

思路:

对于一颗树来说,其实就是统计u到v路径上白边的个数,

加边就是将u到v的路径上所有边都染黑,查询就是查询路径上白边的个数

由于树上每条边最多只会被修改一次,所以可以并查集暴力修改,每个点u指向祖先结点第一条白边的位置。

涂黑白边的操作对应点的子树的答案减一,可以用dfs序树状数组维护

所以u到v路径上黑边的个数就是u,v,减去lca的两倍


#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int> using namespace std;
const int N = 1e5 + 10; void read(int &x){
x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
}
int n,m,q,tot;
struct Edge{int v,nxt;};
Edge e[2 * N];
int head[N];
void add(int u,int v){
e[tot].v = v,e[tot].nxt = head[u],head[u] = tot++;
}
int pa[N];
int Find(int x){return x == pa[x]?x:pa[x] = Find(pa[x]);}
vector<P> res;
int f[N][20],dis[N];
int in[N],out[N],times;
void dfs(int u,int fa,int d){
pa[u] = u,in[u] = ++times;
dis[u] = d,f[u][0] = fa;
for(int i = 1;i <= 18;i++) f[u][i] = f[f[u][i-1]][i-1];
for(int i = head[u];~i;i = e[i].nxt) if(e[i].v != fa) dfs(e[i].v,u,d + 1);
out[u] = times;
}
int LCA(int u,int v){
if(dis[u] < dis[v]) swap(u,v);
int d = dis[u] - dis[v];
for(int i = 18;i >= 0 && u != v;i--) if(d & (1<<i)) u = f[u][i];
if(u == v) return u;
for(int i = 18;i >= 0;i--) if(f[u][i] != f[v][i]) u = f[u][i],v = f[v][i];
return f[u][0];
}
int tr[N],vis[N];
int lowbit(int x){return x&(-x);}
void up(int pos,int c){
for(;pos <= n;pos += lowbit(pos)) tr[pos] += c;
}
int getsum(int pos){
int ans = 0;
for(;pos;pos -= lowbit(pos)) ans += tr[pos];
return ans;
}
void update(int u,int lca){
if(dis[u] <= dis[lca]) return ;
if(!vis[u]) vis[u] = 1,up(in[u],-1),up(out[u]+1,1);
pa[u] = f[u][0];
update(Find(pa[u]),lca);
}
int getans(int u,int v,int lca){
return dis[u] + dis[v] - 2 * dis[lca] + getsum(in[u]) + getsum(in[v]) - 2 * getsum(in[lca]);
}
void init(int n){
times = tot = 0;
for(int i = 1;i <= n;i++){
tr[i] = 0,head[i] = -1,pa[i] = i,vis[i] = 0;
}
res.clear();
}
int main()
{
int T,cas = 1,u,v,op,lca,fu,fv;
cin>>T;
while(T--){
read(n),read(m);
init(n);
for(int i = 0;i < m;i++){
read(u),read(v);
fu = Find(u),fv = Find(v);
if(fu != fv) {add(u,v);add(v,u);pa[fu] = fv;}
else res.push_back(P(u,v));
}
dfs(1,0,0);
for(auto p:res){
u = p.first,v = p.second,lca = LCA(u,v);
update(u,lca),update(v,lca);
}
printf("Case #%d:\n",cas++);
read(q);
while(q--){
read(op),read(u),read(v);
lca = LCA(u,v);
if(op == 1) update(Find(u),lca),update(Find(v),lca);
else printf("%d\n",getans(u,v,lca));
}
}
return 0;
}
上一篇:VMWare 安装 Mac OS X10.10 Yosemite


下一篇:hdu6074[并查集+LCA+思维] 2017多校4