HDU 5458 Stability【树链剖分】

﹏ヽ暗。殇╰゛Y 2022-08-08 15:52 112阅读 0赞

因为保证一定联通，所以我们就可以用一个树链剖分来维护  
我们可以倒过来做，先将图删成一棵树  
然后删除的时候将那条链区间更新为0.  
然后区间求和

#include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define getidx(l,r) (l+r | l!=r)
    #define ls getidx(l,mid)
    #define rs getidx(mid+1,r)
    #define lson l,mid
    #define rson mid+1,r
    #define root 1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=30005;
    const int MAXM=100005;
    const int MAXQ=100005;
    
    int t,n,m,q;
    
    struct edge
    {
        int a,b;
        edge(){}
        edge(int aa,int bb):a(aa),b(bb){}
    
        bool operator < (const edge &o) const
        {
            if(a == o.a)
            {
                return b < o.b;
            }
            return a < o.a;
        }
    };
    
    multiset<edge> S;
    multiset<edge> V;
    
    struct Ans
    {
        int kind;
        int a;
        int b;
        int val;
    }ans[MAXQ];
    
    struct Edge
    {
        int u,v,w;
        int next;
    }e[MAXN<<1];
    
    int head[MAXN],tot;
    int siz[MAXN],p[MAXN],son[MAXN],dep[MAXN];
    int dfn[MAXN],top[MAXN],tim;
    
    int sum[MAXN<<1],la[MAXN<<1];
    
    int bingchafa[MAXN];
    
    int getfather(int x)
    {
        if(bingchafa[x] == x) return x;
        return bingchafa[x] = getfather(bingchafa[x]);
    }
    
    void init()
    {
        CLR(head,-1);CLR(sum,0);
        tot=tim=0;
        for(int i=1;i<=n;i++) bingchafa[i] = i;
        S.clear();
        V.clear();
    }
    
    void addedge(int u,int v,int w)
    {
        e[tot].u=u;e[tot].v=v;e[tot].w=w;
        e[tot].next=head[u];head[u]=tot++;
    }
    
    
    void dfs(int u,int fa=0,int depth=0)
    {
        siz[u]=1;son[u]=-1;
        p[u]=fa;dep[u]=depth;
        for(int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].v;
            if(v==p[u])   continue;
            dfs(v,u,depth+1);
            siz[u]+=siz[v];
            if(son[u]==-1 || siz[v]>siz[son[u]])
                son[u]=v;
        }
    }
    
    void getid(int u,int fa)
    {
        dfn[u]=++tim;top[u]=fa;
        if(son[u]!=-1)
            getid(son[u],fa);
        for(int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].v;
            if(v==p[u] || v==son[u])    continue;
            getid(v,v);
        }
    }
    
    void pushup(int l,int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        sum[idx]=0;
        if(!la[ls])
            sum[idx]+=sum[ls];
        if(!la[rs])
            sum[idx]+=sum[rs];
    }
    
    void pushdown(int l,int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        if(!la[idx])  return;
        la[ls]=la[idx];
        la[rs]=la[idx];
    }
    
    void build(int l,int r)
    {
        int idx=getidx(l,r);
        la[idx]=0;
        if(l==r)
        {
            sum[idx]=1;
            return;
        }
        int mid=MID(l,r);
        build(l,mid);
        build(mid+1,r);
        pushup(l,r);
    }
    
    void update2(int l,int r,int L,int R)
    {
        int idx=getidx(l,r);
        if(L==l && r==R)
        {
            la[idx]=1;
            sum[idx]=0;
            return;
        }
        pushdown(l,r);
        int mid=MID(l,r);
        if(R<=mid)
            update2(l,mid,L,R);
        else if(L>mid)
            update2(mid+1,r,L,R);
        else
            update2(l,mid,L,mid),update2(mid+1,r,mid+1,R);
        pushup(l,r);
    }
    
    int query(int l,int r,int L,int R)
    {
        int idx=getidx(l,r);
        if(la[idx]) return 0;
        if(L==l && r==R)
        {
            return sum[idx];
        }
        int mid=MID(l,r);
        if(R<=mid)
            return query(lson,L,R);
        if(L>mid)
            return query(rson,L,R);
        return query(lson,L,mid)+query(rson,mid+1,R);
    }
    
    void change(int u,int v)
    {
        while(top[u]!=top[v])
        {
            if(dep[top[u]]>dep[top[v]])
                swap(u,v);
            update2(1,tim,dfn[top[v]],dfn[v]);
            v=p[top[v]];
        }
        if(u==v)    return;
        if(dep[u]>dep[v])
            swap(u,v);
        update2(1,tim,dfn[son[u]],dfn[v]);
    }
    
    int query(int u,int v)
    {
        int ans=0;
        while(top[u]!=top[v])
        {
            if(dep[top[u]]>dep[top[v]])
                swap(u,v);
            ans+=query(1,tim,dfn[top[v]],dfn[v]);
            v=p[top[v]];
        }
        if(u==v)    return ans;
        if(dep[u]>dep[v])
            swap(u,v);
        ans+=query(1,tim,dfn[u]+1,dfn[v]);
        return ans;
    }
    
    int main()
    {
        scanf("%d",&t);
    
        for(int cas = 1;cas <= t;cas++)
        {
            scanf("%d%d%d",&n,&m,&q);
    
            init();
            for(int i=1;i<=m;i++)
            {
                edge tmp;
                scanf("%d%d",&tmp.a,&tmp.b);
                if(tmp.a > tmp.b) swap(tmp.a,tmp.b);
                S.insert(tmp);
            }
    
            for(int i=1;i<=q;i++)
            {
                scanf("%d%d%d",&ans[i].kind,&ans[i].a,&ans[i].b);
                if(ans[i].a > ans[i].b) swap(ans[i].a,ans[i].b);
                if(ans[i].kind == 1)
                {
                    multiset<edge>::iterator Pos = S.find(edge(ans[i].a,ans[i].b));
                    S.erase(Pos);
                }
            }
    
            for(multiset<edge>::iterator It = S.begin();It != S.end();++It)
            {
                if(getfather(It->a) != getfather(It->b))
                {
                    bingchafa[getfather(It->a)] = getfather(It->b);
                    V.insert(*It);
                }
            }
    
            for(multiset<edge>::iterator It = V.begin();It != V.end();++It)
            {
                addedge(It->a,It->b,1);
                addedge(It->b,It->a,1);
            }
    
            dfs(1);getid(1,1);
            build(1,tim);
    
            for(multiset<edge>::iterator It = S.begin();It != S.end();++It)
            if(V.find(*It) == V.end())
            {
                change(It->a,It->b);
            }
    
            for(int i=q;i>=1;i--)
            {
                if(ans[i].kind == 1)
                    change(ans[i].a,ans[i].b);
                else if(ans[i].kind == 2)
                    ans[i].val = query(ans[i].a,ans[i].b);
            }
    
            printf("Case #%d:\n",cas);
    
            for(int i=1;i<=q;i++)
            if(ans[i].kind == 2)
                printf("%d\n",ans[i].val);
        }
        return 0;
    }