I know one method in which we do euler tour over the tree and create a depth sequence.Then we find the minimum depth vertex between first and last occurrence of the vertex using any data structure that give RMQ(segment tree,sparse table).

You can turn LCA problem to RMQ±1 and then use Farach Colton Bender algorithm, which solves RMQ±1 in O(n) preprocessing and O(1) for query. Of course sparse table is easier to code and O(n log n) and O(n) don't differ too much for n ~10^5, but since you asked for fastest way...

Btw, fastest way to code LCA is binary lifting

There is an also Tarjan's off-line lowest common ancestors algorithm that uses DSU and works in O(N * DSU).

There is a great tutorial on TopCoder: https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

We have N nodes and Q queries. The best ways of counting LCA are: 1) Segment tree. Dfs the tree with timer, built segment tree and find minimum on segment. O(N + Q * log(N)) 2) Sparse table. Absolutely the same, just find minimum with it. O(N * log(N) + Q) 3) Farach Colton Bender. There is some magic that i don't understand, but it use the fact that two adjacent values in array differs only on 1. You can read about it on e-maxx. However, it's the fastest way to solve LCA. O(N + Q)

I like this offline algorithm: store set of unanswered queries in each vertex, then run dfs and merge sets. Not optimal, but easy to remember, easy to implement, hard to make a bug. Kind of pseudocode:

for i in range(queries):
    q[queries[i][0]].insert(i)
    q[queries[i][1]].insert(i)

def dfs(v, p):
    for to in g[v]:
        if to == p: continue
        dfs(to, v)
        if len(q[v]) < len(q[to]): swap(q[v], q[to])
        for i in q[to]:
            if i in q[v]:
                q[v].delete(i)
                lca[i] = v
            else:
                q[v].insert(i) 

here you can find something good.

Thank you guys!

I read O(N*Sqrt(N)), and reduction of LCA to RMQ technique.

learnt lot many things. and also I can see Tarjan Offline Algo related comments. Can someone provide Time Complexity and links to read it?

Once again, Thank you Codeforces!!