http://codeforces.com/contest/519/problem/E
题意:
给出一棵树和m次询问，每次询问给出两个点，求出到这两个点距离相等的点的个数。
思路:
lca...然后直接判就好了，挂dp标签的人是什么心态。。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 int tot,go[200005],first[200005],next[200005]; 7 int son[200005],fa[200005][19]; 8 int deep[200005]; 9 int n,bin[20]; 10 int read(){ 11 int t=0,f=1;char ch=getchar(); 12 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 13 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 14 return t*f; 15 } 16 void insert(int x,int y){ 17 tot++; 18 go[tot]=y; 19 next[tot]=first[x]; 20 first[x]=tot; 21 } 22 void add(int x,int y){ 23 insert(x,y);insert(y,x); 24 } 25 void dfs(int x,int f){ 26 son[x]=1; 27 for (int i=1;i<=18;i++) 28 fa[x][i]=fa[fa[x][i-1]][i-1]; 29 for (int i=first[x];i;i=next[i]){ 30 int pur=go[i]; 31 if (pur==f) continue; 32 deep[pur]=deep[x]+1; 33 fa[pur][0]=x; 34 dfs(pur,x); 35 son[x]+=son[pur]; 36 } 37 } 38 int lca(int x,int y){ 39 if (deep[x]<deep[y]) std::swap(x,y); 40 int t=deep[x]-deep[y]; 41 for (int i=0;i<=18;i++) 42 if (t&bin[i]) 43 x=fa[x][i]; 44 if (x==y) return x; 45 for (int i=18;i>=0;i--) 46 if (fa[x][i]!=fa[y][i]) 47 x=fa[x][i],y=fa[y][i]; 48 if (x==y) return x; 49 else return fa[x][0]; 50 } 51 void up(int &x,int dep){ 52 int t=deep[x]-dep; 53 for (int i=0;i<=18;i++) 54 if (t&bin[i]) 55 x=fa[x][i]; 56 } 57 void work(int x,int y){ 58 int t=lca(x,y); 59 int len=deep[x]-deep[t]+1+deep[y]-deep[t]+1-1; 60 if (len%2==0){ 61 printf("0\n"); 62 return; 63 } 64 if (x==y){ 65 printf("%d\n",n); 66 return; 67 } 68 if (t==x||t==y){ 69 if (t==x) std::swap(x,y); 70 int tt=x; 71 up(tt,deep[tt]-len/2); 72 up(x,deep[tt]+1); 73 printf("%d\n",son[tt]-son[x]); 74 }else{ 75 if (deep[x]<deep[y]) std::swap(x,y); 76 if (deep[x]==deep[y]){ 77 up(x,deep[t]+1); 78 up(y,deep[t]+1); 79 printf("%d\n",n-son[x]-son[y]); 80 }else{ 81 int tt=x; 82 up(tt,deep[tt]-len/2); 83 up(x,deep[tt]+1); 84 printf("%d\n",son[tt]-son[x]); 85 } 86 } 87 } 88 int main(){ 89 n=read();bin[0]=1;for (int i=1;i<=18;i++) bin[i]=bin[i-1]*2; 90 for (int i=1;i<n;i++){ 91 int x=read(),y=read(); 92 add(x,y); 93 } 94 dfs(1,0); 95 int T=read(); 96 while (T--){ 97 int x=read(),y=read(); 98 work(x,y); 99 } 100 return 0; 101 }