题意
描述
现在有一颗树形状的双向铁路，每条边的行驶时间是\(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 #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 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 '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] >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