http://61.187.179.132/JudgeOnline/problem.php?id=1969

solution.cc

/**************************************************************
    Problem: 1969
    User: zxytim
    Language: C++
    Result: Accepted
    Time:654 ms
    Memory:7568 kb
****************************************************************/
 
/*
 * $File: lane.cpp
 * $Date: Fri Jun 04 07:14:39 2010 +0800
 * $Prob: AHOI2005 lane
 * $Solution:
 *      1. off-line algorithm, deal queries and modification in reverse order
 *      2. LCA -- Sparse Table Algorithm
 *      3. Tree structured arrary -- maintain distance from one node to root
 *      4. Disjoint set -- merge adjacent not-cut edge in the tree
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
 
#define MAXN 30010
#define MAXQ 40010
#define MAXM 100010 * 2
 
#define Lowbit(x) ((x) & (-(x)))
#define OP(x) ((((x) - 1) ^ 1) + 1)
 
using namespace std;
 
class Edge
{
    public:
        int a, b;
};
 
class Query
{
    public:
        int c, a, b, data;
        // when c == 0, data stands for edge id which connect a and b
        // when c == 1, data stands for answer of this query
};
Query query[MAXQ + 1];
Edge e[MAXM + 1];
int Count = 0;
int begin[MAXN + 1], next[MAXM + 1], end[MAXM + 1];
void AddEdge(int a, int b)
{
    Count ++;
    next[Count] = begin[a];
    begin[a] = Count;
    end[Count] = b;
}
 
int n, m, Q;
void Init()
{
    scanf("%d%d", &n, &m);
    int a, b, c;
    for (int i = 1; i <= m; i ++)
    {
        scanf("%d%d", &a, &b);
        if (a > b)
            swap(a, b);
        e[i].a = a, e[i].b = b;
    }
    while (scanf("%d%d%d", &c, &a, &b) == 3)
    {
        Q ++;
        if (a > b)
            swap(a, b);
        query[Q].c = c, query[Q].a = a, query[Q].b = b;
    }
}
 
bool cmpEdge(const Edge &a, const Edge &b)
{
    if (a.a == b.a)
        return a.b < b.b;
    return a.a < b.a;
}
 
int GetEdgeID(int a, int b)
{
    Edge et;
    et.a = a, et.b = b;
    int l = 1, r = m;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (cmpEdge(e[mid], et))
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}
 
bool hashedge[MAXM + 1];
void AddInitEdge()
{
    sort(e + 1, e + 1 + m, cmpEdge);
    for (int i = 1; i <= Q; i ++)
        if (query[i].c == 0)
        {
            query[i].data = GetEdgeID(query[i].a, query[i].b);
            hashedge[query[i].data] = true;
        }
    for (int i = 1; i <= m; i ++)
        if (!hashedge[i])
        {
            AddEdge(e[i].a, e[i].b);
            AddEdge(e[i].b, e[i].a);
        }
}
 
int Log[MAXN * 2 + 1];
int f[MAXN * 2 + 1][19];
int L[MAXN + 1], R[MAXN + 1];
int Father[MAXN + 1];
int dep[MAXN + 1];
bool hash[MAXN + 1];
int N = 0;
bool intree[MAXM + 1];
void dfs(int x)
{
    hash[x] = true;
    N ++;
    f[N][0] = x;
    L[x] = N;
    for (int now = begin[x]; now; now = next[now])
        if (!hash[end[now]])
        {
            intree[now] = intree[OP(now)] = true;
            Father[end[now]] = x;
            dep[end[now]] = dep[x] + 1;
            dfs(end[now]);
            f[++N][0] = x;
        }
    R[x] = N;
}
 
int c[MAXN * 2 + 1];
void Add(int p, int v)
{
    while (p <= N)
        c[p] += v, p += Lowbit(p);
}
 
int Sum(int p)
{
    int ret = 0;
    while (p)
        ret += c[p], p -= Lowbit(p);
    return ret;
}
 
int LCA(int a, int b)
{
    a = L[a], b = L[b];
    if (a > b)
        swap(a, b);
    int k = Log[b - a + 1];
    int id1 = f[a][k], id2 = f[b - (1 << k) + 1][k];
    if (dep[id1] < dep[id2])
        return id1;
    return id2;
}
 
int father[MAXN + 1];
int Getfather(int x)
{
    if (x == father[x])
        return x;
    return father[x] = Getfather(father[x]);
}
 
 
void CoverRoute(int a, int fa)
{
    while (dep[a] > dep[fa])
    {
        a = Getfather(a);
        if (dep[a] > dep[fa])
        {
            Add(L[a], -1);
            Add(R[a] + 1, 1);
            father[a] = Father[a];
        }
    }
}
 
void Cover(int a, int b)
{
    int fa = LCA(a, b);
    CoverRoute(a, fa);
    CoverRoute(b, fa);
}
 
void Init_LCA_Dist_DisjointSet_Tree()
{
    dfs(1);
    // Init LCA
    for (int i = 0; (1 << i) <= N; i ++)
        for (int j = (1 << i); j < (1 << (i + 1)) && j <= N; j ++)
            Log[j] = i;
    int t;
    for (int j = 1; (1 << j) <= N; j ++)
        for (int i = 1; i <= N; i ++)
        {
            f[i][j] = f[i][j - 1];
            t = i + (1 << (j - 1));
            if (t <= N)
            {
                if (dep[f[t][j - 1]] < dep[f[i][j]])
                    f[i][j] = f[t][j - 1];
            }
        }
    // Init Dist
    for (int i = 1; i <= n; i ++)
    {
        Add(L[i], 1);
        Add(R[i] + 1, -1);
    }
    // Init disjoint set
    for (int i = 1; i <= n; i ++)
        father[i] = i;
    // Init Tree
    for (int i = 1; i <= n; i ++)
        for (int now = begin[i]; now; now = next[now])
            if (!intree[now])
            {
                intree[now] = intree[OP(now)] = true;
                Cover(i, end[now]);
            }
}
 
 
int Ask(int a, int b)
{
    int fa = LCA(a, b);
    return Sum(L[a]) + Sum(L[b]) - Sum(L[fa]) * 2;
}
 
void DealQuery()
{
    for (int i = Q; i >= 1; i --)
        if (query[i].c == 0)
            Cover(query[i].a, query[i].b);
        else
            query[i].data = Ask(query[i].a, query[i].b);
}
 
void Solve()
{
    AddInitEdge();
    Init_LCA_Dist_DisjointSet_Tree();
    DealQuery();
}
 
void Print()
{
    for (int i = 1; i <= Q; i ++)
        if (query[i].c == 1)
            printf("%d\n", query[i].data);
}
 
int main()
{
    Init();
    Solve();
    Print();
    return 0;
}