我真是tcl居然没有调出来。
首先套路地拆成上行和下行两端。
先考虑上行,对于一个点\(u\)如果满足条件那么它一定满足\(d_l-d_{u}=u\)
移项得到\(d_l=d_u+u\)
这不是链上数一个数的个数吗,dfs的时候差分询问开桶记录即可。
然后下行也是一样的。
总的时间复杂度\(O(mlogn+n)\)时间复杂度瓶颈在lca上。
code:
#include<bits/stdc++.h> #include<set> #define ll long long #define re register #define I inline #define N 300000 #define M 100 #define W 100000 #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define Me(x,y) memset(x,y,sizeof(x)) #define it iterator #define Gc() getchar() using namespace std; int n,m,xs,ys,x[N+5],y[N+5],z[N+5],fa[N+5],d[N+5],top[N+5],siz[N+5],son[N+5],Ans[N+5],F[N+5<<1]; struct yyy{int to,z;}; struct ljb{ int head,h[N+5];yyy f[N+5<<1]; I void add(int x,int y){f[++head]=(yyy){y,h[x]};h[x]=head;} }s; struct ques{int id,x,flag;}now;vector<ques> Q[N+5]; I void dfs1(int x,int last){ d[x]=d[last]+1;siz[x]=1;fa[x]=last;yyy tmp;for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^last&&(dfs1(tmp.to,x),siz[x]+=siz[tmp.to],siz[tmp.to]>siz[son[x]]&&(son[x]=tmp.to)); } I void dfs2(int x,int last){ top[x]=last;if(!son[x]) return;yyy tmp;dfs2(son[x],last);for(int i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^fa[x]&&tmp.to^son[x]&&(dfs2(tmp.to,tmp.to),0); } I int lca(int x,int y){while(top[x]^top[y]) d[top[x]]>d[top[y]]?(x=fa[top[x]]):y=(fa[top[y]]);return d[x]>d[y]?y:x;} I void GetAns1(int x){ F[d[x]+x]++;int i;yyy tmp;for(i=0;i<Q[x].size();i++) now=Q[x][i],Ans[now.id]+=F[now.x]*now.flag; for(i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^fa[x]&&(GetAns1(tmp.to),0);F[d[x]+x]--; } I void GetAns2(int x){ F[x-d[x]+n]++;int i;yyy tmp;for(i=0;i<Q[x].size();i++) now=Q[x][i],Ans[now.id]+=F[now.x+n]*now.flag; for(i=s.h[x];i;i=tmp.z) tmp=s.f[i],tmp.to^fa[x]&&(GetAns2(tmp.to),0);F[x-d[x]+n]--; } I void read(int &x){ char s=getchar();x=0;while(s<'0'||s>'9') s=Gc(); while(s>='0'&&s<='9') x=x*10+s-48,s=Gc(); } int main(){ freopen("d.in","r",stdin);freopen("d.out","w",stdout); re int i,j;scanf("%d%d",&n,&m);for(i=1;i<n;i++) read(xs),read(ys),s.add(xs,ys),s.add(ys,xs);dfs1(1,0);dfs2(1,1); for(i=1;i<=m;i++) read(x[i]),read(y[i]),z[i]=lca(x[i],y[i]),Q[x[i]].push_back((ques){i,d[x[i]],1}),Q[fa[z[i]]].push_back((ques){i,d[x[i]],-1});GetAns1(1); for(i=1;i<=n;i++) Q[i].clear();for(i=1;i<=m;i++) Q[y[i]].push_back((ques){i,d[x[i]]-2*d[z[i]],1}),Q[z[i]].push_back((ques){i,d[x[i]]-2*d[z[i]],-1});GetAns2(1); for(i=1;i<=m;i++) printf("%d\n",Ans[i]); }