####Description
####Input ####Output ####Sample Input3 3 1
1 2 2 3 1 2 3 1 1 3 3 1 3####Sample Output
1
1 3####Data Constraint
###题解:
本题看上去很奇怪,首席先我们看一个题解: 我们发现,本题的数据有分支,于是有的点可以用线段树,有的点可以用Tarjan搞LCA。而且正解特别简单,但是比较弱弱的我,傻逼地打了个树链剖分。 于是我们来讲讲: 首先,我们在题解中发现,求A到C与B到C的答案等于求A到C加B到C减去A到B。 于是我们借用树链剖分的思路,来搞搞,但是本人一时头脑发热,一下子把50%分的方法的一个部分用在的树链剖分里,于是时间变得特别地慢。有兴趣的童鞋可以研究研究。 Code:uses math;var i,j,k,l,n,m,num,x,y,tot,ans,gs,a,b,c:longint; tov,last,next,siz,son,dep,fa,tree,pre,top,f:array[1..800000] of int64;procedure maketree(x,st,en:longint);var m:longint;begin if st=en then f[x]:=1 else begin m:=(st+en) div 2; maketree(x*2,st,m); maketree(x*2+1,m+1,en); f[x]:=f[x*2]+f[x*2+1]; end;end;procedure find(x,st,en,l,r:longint);var m:longint;begin if (st=l) and (en=r) then ans:=ans+f[x] else begin m:=(st+en) div 2; if r<=m then find(x*2,st,m,l,r) else begin if l>m then find(x*2+1,m+1,en,l,r) else begin find(x*2,st,m,l,m); find(x*2+1,m+1,en,m+1,r); end; end; end;end;procedure dfsfd(v,f,d:longint);var i,j,k,l:longint;begin fa[v]:=f; dep[v]:=d; siz[v]:=1; i:=last[v]; while i<>0 do begin if tov[i]<>fa[v] then begin dfsfd(tov[i],v,d+1); siz[v]:=siz[v]+siz[tov[i]]; if (son[v]=0) or (siz[tov[i]]>siz[son[v]]) then son[v]:=tov[i]; end; i:=next[i]; end;end;procedure dfs(v,num:longint);var i,j,k,l:longint;begin inc(gs); tree[v]:=gs; top[v]:=num; pre[gs]:=v; if son[v]=0 then exit; dfs(son[v],num); i:=last[v]; while i<>0 do begin if tov[i]<>fa[v] then begin if tov[i]<>son[v] then begin dfs(tov[i],tov[i]); end; end; i:=next[i]; end;end;function getans(x,y:longint):longint;var i,j,tx,ty,k:longint;begin tx:=top[x]; ty:=top[y]; k:=0; while tx<>ty do begin if dep[tx]dep[y] then begin ans:=0; find(1,1,n,tree[y],tree[x]); k:=k+ans; end else begin ans:=0; find(1,1,n,tree[x],tree[y]); k:=k+ans; end; exit(k);end;procedure insert(x,y:longint);begin inc(tot); tov[tot]:=y; next[tot]:=last[x]; last[x]:=tot;end;begin //assign(input,'0data.in');reset(input); //assign(output,'0data.out');rewrite(output); readln(n,m,num); for i:=1 to n-1 do begin readln(x,y); insert(x,y); insert(y,x); end; maketree(1,1,n); dfsfd(1,0,1); dfs(1,1); for i:=1 to m do begin readln(a,b,c); writeln((getans(a,b)+getans(c,b)-getans(a,c))div 2+1); end;end.