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，预处理点到根节点的距离，再根据LCA是不是根节点决定距离相减或相加就可以了。
考虑100分的，仍然要LCA，然后分类讨论就可以了......
我们记num[i]为i到根节点的点的个数（包括根节点和它自己）
第一种是LCAab和LCAcb相等，那么我们求LCAac,答案就是num[LCAac]+num[B]-num[LCAab]+1。（这里的一个点到根节点的个数包括根节点和它本身。）
第二种是LCAab和LCAcb不相等，如果LCAab和LCAcb中有一个是B的，那么答案就是1，如果都不是B，那么我们再求LCALCAab LCAcb，这个时候它们的LCA必是其中的一个（可用反证法证明），如果是LCAab，那么答案就是num[B]-num[LCAcb]+1，否则就是LCAcb，答案为num[B]-num[LCAab]+1。
LCA用树上倍增或者欧拉迹+ST就可以啦（欧拉迹数组似乎要开很大QAQRE好久）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #define N 600001 8 using namespace std; 9 int n,m,p,t,ans,head[N*2],next[N*2],to[N*2],visit[N],deep[N*2],ji[N*2],num,ti,ge[N],f[N][100],qwq[N][100]; 10 void add(int u,int v){ 11 num++; 12 next[num]=head[u]; 13 to[num]=v; 14 head[u]=num; 15 num++; 16 next[num]=head[v]; 17 to[num]=u; 18 head[v]=num; 19 } 20 void dfs(int x,int nu,int d){ 21 if (!visit[x]) visit[x]=++ti; 22 ji[ti]=x; 23 deep[ti]=d; 24 ge[x]=nu; 25 for (int i=head[x],v;i!=0;i=next[i]){ 26 v=to[i]; 27 if (!visit[v]) { 28 dfs(v,nu+1,d+1); 29 ji[++ti]=x; 30 deep[ti]=d; 31 } 32 } 33 } 34 void ST(){ 35 int tmp=(int)(log(ti)/log(2)); 36 for (int i=1;i<=ti;i++){ 37 f[i][0]=deep[i]; 38 qwq[i][0]=ji[i]; 39 } 40 for (int j=1;j<=tmp;j++) 41 for (int i=1;i<=ti;i++){ 42 int k=1<<(j-1); 43 if (i-k<=ti) 44 if (f[i][j-1]<f[i+k][j-1]){ 45 f[i][j]=f[i][j-1]; 46 qwq[i][j]=qwq[i][j-1]; 47 } 48 else{ 49 f[i][j]=f[i+k][j-1]; 50 qwq[i][j]=qwq[i+k][j-1]; 51 } 52 } 53 } 54 int lca(int x,int y){ 55 int a=min(visit[x],visit[y]); 56 int b=max(visit[y],visit[x]); 57 int tmp=(int)(log((b-a)+1)/log(2)); 58 if (f[a][tmp]<f[b-(1<<(tmp))+1][tmp]) 59 return qwq[a][tmp]; 60 else return qwq[b-(1<<(tmp))+1][tmp]; 61 } 62 void work(int a,int b,int c){ 63 int d=0,e=0; 64 d=lca(a,b); 65 e=lca(b,c); 66 if (d==e){ 67 int x=lca(a,c); 68 printf("%d\n",ge[x]+ge[b]-2*ge[d]+1); 69 } 70 else if ((d==b)||(e==b)) printf("1\n"); 71 else { 72 int x=lca(d,e); 73 if (x==d) printf("%d\n",ge[b]-ge[e]+1); 74 else if (x==e) printf("%d\n",ge[b]-ge[d]+1); 75 } 76 } 77 int main(){ 78 scanf("%d%d%d",&n,&m,&p); 79 for (int i=1,u,v;i<n;i++){ 80 scanf("%d%d",&u,&v); 81 add(u,v); 82 } 83 dfs(1,1,0); 84 ST(); 85 for (int i=1,u,v,w;i<=m;i++){ 86 scanf("%d%d%d",&u,&v,&w); 87 work(u,v,w); 88 } 89 return 0; 90 }
（似乎JZ评测集下会爆栈...根节点设为n/2也可以）（明明20万数据莫名60万才过了QAQ）
还有一个水水的程序（输入数据还好良心，告诉你性质）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #define N 500001 8 using namespace std; 9 int n,m,p,t,ans,head[N*2],next[N*2],to[N*2],visit[N],deep[N*2],ji[N*2],num,ti,ge[N],f[N][100],qwq[N][100]; 10 void add(int u,int v){ 11 num++; 12 next[num]=head[u]; 13 to[num]=v; 14 head[u]=num; 15 num++; 16 next[num]=head[v]; 17 to[num]=u; 18 head[v]=num; 19 } 20 void shui1(){ 21 for (int i=1,u,v,w;i<=m;i++){ 22 scanf("%d%d%d",&u,&v,&w); 23 if ((v>=u)&&(v>=w)) printf("%d\n",v-max(u,w)+1); 24 else if (((v>=u)&&(v<=w))||(v<=u)&&v>=w) printf("1\n"); 25 else if ((v<=u)&&(v<=w)) printf("%d\n",min(u,w)-v+1); 26 } 27 } 28 void dfs(int x,int nu,int d){ 29 if (!visit[x]) visit[x]=++ti; 30 ji[ti]=x; 31 deep[ti]=d; 32 ge[x]=nu; 33 for (int i=head[x],v;i!=0;i=next[i]){ 34 v=to[i]; 35 if (!visit[v]) { 36 dfs(v,nu+1,d+1); 37 ji[++ti]=x; 38 deep[ti]=d; 39 } 40 } 41 } 42 void ST(){ 43 int tmp=(int)(log(ti)/log(2)); 44 for (int i=1;i<=ti;i++){ 45 f[i][0]=deep[i]; 46 qwq[i][0]=ji[i]; 47 } 48 for (int j=1;j<=tmp;j++) 49 for (int i=1;i<=ti;i++){ 50 int k=1<<(j-1); 51 if (i-k<=ti) 52 if (f[i][j-1]<f[i+k][j-1]){ 53 f[i][j]=f[i][j-1]; 54 qwq[i][j]=qwq[i][j-1]; 55 } 56 else{ 57 f[i][j]=f[i+k][j-1]; 58 qwq[i][j]=qwq[i+k][j-1]; 59 } 60 } 61 } 62 int lca(int x,int y){ 63 int a=min(visit[x],visit[y]); 64 int b=max(visit[y],visit[x]); 65 int tmp=(int)(log((b-a)+1)/log(2)); 66 if (f[a][tmp]<f[b-(1<<(tmp))+1][tmp]) 67 return qwq[a][tmp]; 68 else return qwq[b-(1<<(tmp))+1][tmp]; 69 } 70 void shui2(){ 71 for (int i=1,u,v,w,x;i<=m;i++){ 72 scanf("%d%d%d",&u,&v,&w); 73 x=lca(u,v); 74 if (x==1) printf("%d\n",ge[u]+ge[v]-1); 75 else printf("%d\n",ge[u]+ge[v]-2*ge[x]+1); 76 } 77 } 78 void work(int a,int b,int c){ 79 int d=0,e=0; 80 d=lca(a,b); 81 e=lca(b,c); 82 if (d==e){ 83 int x=lca(a,c); 84 printf("%d\n",ge[x]+ge[b]-2*ge[d]+1); 85 } 86 else if ((d==b)||(e==b)) printf("1\n"); 87 else { 88 int x=lca(d,e); 89 if (x==d) printf("%d\n",ge[b]-ge[e]+1); 90 else if (x==e) printf("%d\n",ge[b]-ge[d]+1); 91 } 92 } 93 int main(){ 94 scanf("%d%d%d",&n,&m,&p); 95 for (int i=1,u,v;i<n;i++){ 96 scanf("%d%d",&u,&v); 97 add(u,v); 98 } 99 if ((p==11)||(p==12)||(p==13)||(p==17)||(p==18)){ 100 shui1(); return 0; 101 } 102 ti=0; 103 dfs(1,1,0); 104 ST(); 105 if ((p==14)||(p==15)||(p==19)){ 106 shui2(); return 0; 107 } 108 for (int i=1,u,v,w;i<=m;i++){ 109 scanf("%d%d%d",&u,&v,&w); 110 work(u,v,w); 111 } 112 return 0; 113 }
