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;

}