现在有一颗树形状的双向铁路，每条边的行驶时间是\(1\)；
给出\(m\)条列车行驶的路径\(s_{i}\to t_{i}\)，问列车相遇的对数(无序对)；
\(i和j\)号列车相遇当且仅当存在某个时刻使得\(i\)和\(j\)在同一个位置，注意这个位置可能在点上，也可能在边上；
$0 \le n ,m \le 10^5 $
相遇只有两种，同向和逆向；
把边也拆成点可以解决在边上相遇的问题；
考虑把每条路径按深度的大小关系划分成上行和下行(lca在上行)；
这样就只需要考虑上行和上行相交，上行和下行分别相交；
上行和上行相加直接统计子树内出发深度相同的路径的个数；
上行和下行相交树剖后变为一次函数\(x+c\)和\(-x+c\)的交点个数；
逆时针旋转\(45^{\circ}\) 之后做扫描线+\(BIT\)即可；
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N=200100,M=20;
int n,m,o=1,hd[N];
int size[N],sn[N],tp[N],fa[N],idx,st[N],id[N],dep[N];
int sz,rt[N],ls[N*M],rs[N*M],sum[N*M],cnt1,cnt2,c[N<<1];
struct Edge{int v,nt;}E[N<<1];
vector<int>vec[N];
struct data{
int x,p,typ;
data(int _x=0,int _p=0,int _typ=0):x(_x),p(_p),typ(_typ){};
bool operator <(const data&A)const{return p<A.p;}
}l1[N*M],l2[N*M];
ll ans;
char gc(){
static char*p1,*p2,s[1000000];
if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
return(p1==p2)?EOF:*p1++;
}
int rd(){
int x=0;char c=gc();
while(c<'0'||c>'9')c=gc();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
return x;
}
void adde(int u,int v){
E[o]=(Edge){v,hd[u]};hd[u]=o++;
E[o]=(Edge){u,hd[v]};hd[v]=o++;
}
void dfsA(int u,int F){
size[u]=1;sn[u]=0;
dep[u]=dep[fa[u]=F]+1;
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==F)continue;
dfsA(v,u);
size[u]+=size[v];
if(size[v]>size[sn[u]])sn[u]=v;
}
}
void dfsB(int u,int T){
st[++idx]=u;id[u]=idx;tp[u]=T;
if(sn[u])dfsB(sn[u],T);
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==fa[u]||v==sn[u])continue;
dfsB(v,v);
}
}
int lca(int u,int v){
int tu=tp[u],tv=tp[v];
while(tu!=tv){
if(dep[tu]<dep[tv])swap(u,v),swap(tu,tv);
u=fa[tu],tu=tp[u];
}
return dep[u]<dep[v]?u:v;
}
int go(int u,int d){
if(d<0)return 0;
int tu=tp[u];
while(dep[u]-dep[tu]<d){
d-=dep[u]-dep[tu]+1;
u=fa[tu],tu=tp[u];
}
return st[id[u]-d];
}
void update(int&k,int l,int r,int x,int y){
if(!k)k=++sz;
sum[k]+=y;
if(l==r)return;
int mid=l+r>>1;
if(x<=mid)update(ls[k],l,mid,x,y);
else update(rs[k],mid+1,r,x,y);
}
void merge(int&x,int&y){
if(!x||!y){x=x+y;return;}
if(!ls[x]&&!rs[x]){
sum[x]=sum[x]+sum[y];
return ;
}
merge(ls[x],ls[y]);
merge(rs[x],rs[y]);
sum[x]=sum[ls[x]]+sum[rs[x]];
}
int query(int k,int l,int r,int x){
--sum[k];
if(l==r)return sum[k];
int mid=l+r>>1;
if(x<=mid)return query(ls[k],l,mid,x);
else return query(rs[k],mid+1,r,x);
}
void dfsC(int u){
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==fa[u])continue;
dfsC(v);
merge(rt[u],rt[v]);
}
for(int i=0;i<vec[u].size();++i){
int v=vec[u][i];
ans+=query(rt[u],1,n,dep[v]);
}
}
void init1(int x1,int y1,int x2,int y2){
int x,y,z;
x=x1-y1+n;
y=x2-y2+n;
z=x1+y1;
l1[++cnt1]=data(x-1,z,-1);
l1[++cnt1]=data(y,z,1);
}
void init2(int x1,int y1,int x2,int y2){
int x,y,z;
x=x1+y1;
y=x2+y2;
z=x1-y1+n;
l2[++cnt2]=data(z,x,1);
l2[++cnt2]=data(z,y+1,-1);
}
void add(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}
int ask(int x){int re=0;for(;x;x-=x&-x)re+=c[x];return re;}
int main(){
freopen("train.in","r",stdin);
freopen("train.out","w",stdout);
n=rd();
for(int i=1;i<n;++i){
int u=rd(),v=rd();
adde(u,i+n),adde(v,i+n);
}
dfsA(1,0);
dfsB(1,1);
n<<=1;m=rd();
int dg=0;
for(int i=1,u,v,p,q,tu,tv,d;i<=m;++i){
u=rd();v=rd();p=lca(u,v);
q=go(v,dep[v]-dep[p]-1);
if(dg){
printf("%d %d %d %d\n",u,v,p,q);
}
update(rt[u],1,n,dep[u],1);
vec[p].pb(u);
tu=tp[u];d=0;
while(tu!=tp[p]){
init1(id[tu],d+dep[u]-dep[tu],id[u],d);
d+=dep[u]-dep[tu]+1;
u=fa[tu],tu=tp[u];
}
init1(id[p],d+dep[u]-dep[p],id[u],d);
d+=dep[u]-dep[p];
if(v==p)continue;
tv=tp[v];d+=dep[v]-dep[p];
while(tv!=tp[q]){
init2(id[tv],d-dep[v]+dep[tv],id[v],d);
d-=dep[v]-dep[tv]+1;
v=fa[tv],tv=tp[v];
}
init2(id[q],d-dep[v]+dep[q],id[v],d);
d-=dep[v]-dep[q];
}
dfsC(1);
sort(l1+1,l1+cnt1+1);
sort(l2+1,l2+cnt2+1);
n<<=1;
for(int i=1,j=1;i<=cnt1;++i){
while(j<=cnt2&&l2[j].p<=l1[i].p){
add(l2[j].x,l2[j].typ);
j++;
}
ans+=l1[i].typ*ask(l1[i].x);
}
printf("%lld\n",ans);
return 0;
}原文：https://www.cnblogs.com/Paul-Guderian/p/10574113.html