Description
Input
Output
Sample Input
3 3 11 22 31 2 31 1 33 1 3
Sample Output
113
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 #include2 #include 3 #include 4 #include 5 #include 6 #include 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]
（似乎JZ评测集下会爆栈...根节点设为n/2也可以）（明明20万数据莫名60万才过了QAQ）
还有一个水水的程序（输入数据还好良心，告诉你性质）
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 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]