[IOI Camp Judge 53]鋪路問題

IOI Camp Judge是暫時性的，因此我在這裡做了題目備份，請大家參考～

這裡提供另外一種做法，輸出正確，但不一定能AC

我們先來觀察一下，在把一條一條邊加進去的時候，重要道路的數量會有甚麼變化呢？
仔細想想可以發現，只有以下三種情況會發生：
1. 兩顆不連通的樹接在一起，重要道路數量增加$1$
2. 樹上形成一個環，重要道路數量減少「環的大小-1」，環上的所有點之後可以視為同一點
3. 自環(這是有可能的，因為2.會把環上所有點視作同一點)，可忽略

學過動態樹的同學們可能就開始刻伸展樹、維護父節點、Access(u)之類的
事實上......
我為了解這題跑去學了link-cut tree，好不容易近200行寫出來了，傳上去TLE......
如果想看這份code，請參考這裡(輸出是正確的哦www)

往離線的方向思考，如果我們已經預知了未來這些樹會長甚麼樣子，會怎麼樣呢？
來看看這時後如果遇到前述的三種情況會發生甚麼事吧www

1. 兩顆不連通的樹接在一起，重要道路數量增加$1$
　可以用disjoint set判斷，而且可以保證加進去的邊一定是未來樹的邊(想一想，為甚麼XD)，未來樹慢慢成長中www

2. 樹上形成一個環，重要道路數量減少「環的大小-1」，環上的所有點之後可以視為同一點
　可以保證長到一半的未來樹已經讓這兩點連通了(想一想，為甚麼XD)，如果對未來樹做父節點的預處理，可以再用另一個disjoint set，一步一步往LCA(longest common ancestor)的方向走，一邊把點合併，實現時間複雜度$O((環的大小-1)\alpha(N))$的縮環！

3. 自環(這是有可能的，因為2.會把環上所有點視作同一點)，可忽略
　不用管它，不過要注意，continue別亂用XD

因此，我們只需要兩個disjoint set，一個維護連通性，另一個維護縮環操作
需要預處理每個節點的父節點，還有節點的深度(因為縮環時要一步一步往LCA走，深度深的點要先走)

時間複雜度：$O((N+K+M)+(K+M)\alpha(N))$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge
{
    const int a,b;
    Edge():a(),b(){}
    Edge(const int _a,const int _b):a(_a),b(_b){}
};
vector<Edge>EDGE;
struct Djset
{
    int s[100000];
    void clear(const int n){for(int i=0;i<n;i++)s[i]=i;}
    int find(const int a){return s[a]==a?a:(s[a]=find(s[a]));}
    bool merge(int a,int b){if((a=find(a))==(b=find(b)))return false;s[a]=b;return true;}
    int operator[](const int a){return find(a);}
}ID,COMP;
vector<int>ET[100000];
int PARENT[100000],DEPTH[100000];
void MarkParent(const int u,const int parent,const int depth)
{
    assert(PARENT[u]==-2);
    PARENT[u]=parent,DEPTH[u]=depth;
    for(const int nxt:ET[u])if(nxt!=parent)MarkParent(nxt,u,depth+1); 
}
int N,K,M;
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d%d",&N,&K);
        EDGE.clear();
        for(int a,b,i=0;i<K;i++)scanf("%d%d",&a,&b),EDGE.push_back(Edge(--a,--b));
        scanf("%d",&M);
        for(int a,b,i=0;i<M;i++)scanf("%d%d",&a,&b),EDGE.push_back(Edge(--a,--b));
        for(int i=0;i<N;i++)ET[i].clear();
        COMP.clear(N);
        for(const Edge &e:EDGE)if(COMP.merge(e.a,e.b))ET[e.a].push_back(e.b),ET[e.b].push_back(e.a);
        for(int i=0;i<N;i++)PARENT[i]=-2;
        for(int u=0;u<N;u++)if(PARENT[u]==-2)MarkParent(u,-1,0);
        COMP.clear(N);
        ID.clear(N);
        assert(K+M==(int)EDGE.size());
        for(int i=0,ans=0;i<K+M;i++)
        {
            const Edge &e=EDGE[i];
            int a=ID[e.a],b=ID[e.b];
            if(a!=b)
            {
                if(COMP[a]!=COMP[b])COMP.merge(a,b),ans++;
                else
                {
                    while(a!=b)
                    {
                        if(DEPTH[b]>DEPTH[a])swap(a,b);
                        assert(DEPTH[a]>=DEPTH[b]);
                        ID.merge(a,PARENT[a]),a=ID[a],ans--;
                    }
                }
            }
            if(i>=K)printf("%d\n",ans);
        }
    }
    return 0;
}