JZOJ5257. 小X的佛光(2017.8B组)

Description

Input

Output

Sample Input

3 3 1
1 2
2 3
1 2 3
1 1 3
3 1 3

Sample Output

1
1
3

Data Constraint

想法：
暴力的LCA很多分
其实答案=(jl(x,y)+jl(y,z)-jl(x,z))/2+1
jl（x,y）=len[x]+len[y]-len[lca]*2;
len为某个点的深度，lca为最短公共祖先
如何快速求lca
用father[i][x]记录第i个点的第2^x个父亲
x，y的lca
先求出len[x],len[y]的差，然后把这个差二进制一下，i=1~20,如果二进制第i位为1
向上跳2^(j-1)
然后同时向上跳，如果father[x][i]<>father[y][i]那么肯定往上跳
如果lca是他们的第2^j个父亲，那么如果当前x，y不相同，同时向上跳1个，肯定相同