经过部分分的提示，我们可以把一条路径切成s到lca 和lca到t的链

这样就分为向上的链和向下的链，我们分开考虑：

向上：如果某一个链i可以对点x产生贡献，那么有deep[x]+w[x]=deep[S[i]]，而且S[i]和lca[i]都在x的子树中

向下：如果某一个链i可以对点x产生贡献，那么有deep[x]-w[x]=deep[T[i]]-L[i]，而且T[i]和lca[i]都在x的子树中，其中L[i]表示对应的路径的长度，即L[i]=deep[T[i]]+deep[S[i]]-2*deep[lca[i]]

这样的话，我们可以把deep[S[i]]和deep[T[i]]-L[i]在合适的时候放到对应的桶里，然后在合适的时候查桶里的值作为答案

具体来说，dfs一下，找到S（或T）的时候给对应的桶++，找到lca的时候给对应的桶--，在子树都做完以后统计答案

但只是这样的话，对于某些点，会出现某些链，lca在它的祖先上，但端点却在它的祖先的另一颗子树中，也就是会被这个点查到

我们只要在进入这个点的时候记下来进入时候对应的桶中的结果，再在回来的时候用现在的减掉刚才记下来的，就是答案，因为这样减出来的一定是在他子树里的

注意由于偷懒，lca实际上在这两个链里都算了一遍，如果lca会被它这个点统计到的话，需要减下去一次贡献

据说有差分的思想？我太菜了看不出来...

1 #include
     
       2 #define pa pair
      
        3 #define lowb(x) ((x)&(-(x))) 4 #define REP(i,n0,n) for(i=n0;i<=n;i++) 5 #define PER(i,n0,n) for(i=n;i>=n0;i--) 6 #define MAX(a,b) ((a>b)?a:b) 7 #define MIN(a,b) ((a
       
        '9'){
   if(c=='-') neg=-1;c=getchar();}17     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();18     return x*neg;19 }20 21 struct Edge{22     int a,b,ne;23 }eg[maxn*2];24 int egh[maxn],ect;25 int N,M,w[maxn],s[maxn],t[maxn];26 int dep[maxn],lca[maxn],len[maxn],bfa[maxn];27 int fa[maxn],que[maxn*2][2],qh[maxn];28 int cntu[maxn],cntd[maxn*2],ans[maxn];29 int sid[maxn],sh[maxn],tid[maxn],th[maxn],lid[maxn],lh[maxn];30 bool flag[maxn];31 32 inline void adeg(int a,int b){33     eg[++ect].a=a;eg[ect].b=b;eg[ect].ne=egh[a];egh[a]=ect;34 }35 inline int getf(int x){
   return x==bfa[x]?x:bfa[x]=getf(bfa[x]);}36 37 void dfs(int x){38     flag[x]=1;39     for(int i=egh[x];i;i=eg[i].ne){40         int b=eg[i].b;41         if(flag[b]) continue;42         dep[b]=dep[x]+1;fa[b]=x;43         dfs(b);44         bfa[getf(b)]=getf(x);45     }46     for(int i=qh[x];i;i=que[i][1]){47         if(flag[que[i][0]]) lca[i>>1]=getf(que[i][0]);48     }49 }50 51 void solve(int x,int f){52     int su=cntu[dep[x]+w[x]],sd=cntd[dep[x]-w[x]+N];53     for(int i=sh[x];i;i=sid[i]){54         cntu[dep[s[i]]]++;55     }for(int i=th[x];i;i=tid[i]){56         cntd[dep[t[i]]-len[i]+N]++;57     }58     for(int i=egh[x];i;i=eg[i].ne){59         int b=eg[i].b;60         if(b==f) continue;61         solve(b,x);62     }63     ans[x]=cntu[dep[x]+w[x]]+cntd[dep[x]-w[x]+N]-su-sd;64     for(int i=lh[x];i;i=lid[i]){65         cntu[dep[s[i]]]--;66         cntd[dep[t[i]]-len[i]+N]--;67         if(w[x]==dep[s[i]]-dep[lca[i]]) ans[x]--;68     }69 }70 71 int main(){72     int i,j,k;73     N=rd(),M=rd();74     for(i=1;i