题目大意：给出N(1 <= N <= 200000)个结点的树，求长度等于K(1 <= K <= 1000000)的路径的最小边数

树的点分治，统计方法同POJ1741，不过比较讨厌的一点是最小值不支持区间减法，所以直接把所有路经长=k的方案都计入ans，然后就可以相减了，最后从左到右扫一遍即可~

写的好慢。。。基本就是卡时过的 RANK1那家伙到底写了啥。。。

#include
  
   
#include
   
     #include
    
      #include
     
       #define M 200200 using namespace std; struct abcd{ int to,f,next; bool ban; }table[M<<1]; int head[M],tot=1; int n,k; int siz[M],fa[M],ans[M],dis[M],dpt[M]; pair
      
       stack[M];int top; void Find_Centre_Of_Gravity(int x,int size,int &cg) { int i; bool flag=1; siz[x]=1; for(i=head[x];i;i=table[i].next) { if(table[i].to==fa[x]||table[i].ban) continue; fa[table[i].to]=x; Find_Centre_Of_Gravity(table[i].to,size,cg); siz[x]+=siz[table[i].to]; if(siz[table[i].to]>size>>1) flag=0; } if(size-siz[x]>size>>1) flag=0; if(flag) cg=x; } void DFS1(int x,int d,int deep,int from) { int i; dis[x]=d; dpt[x]=deep; fa[x]=from; for(i=head[x];i;i=table[i].next) { if(table[i].to==fa[x]||table[i].ban) continue; DFS1(table[i].to,d+table[i].f,deep+1,x); } } void DFS2(int x) { int i; stack[++top]=make_pair(dis[x],dpt[x]); for(i=head[x];i;i=table[i].next) { if(table[i].to==fa[x]||table[i].ban) continue; DFS2(table[i].to); } } void Calculate(int x,int flag) { int i,j,l; top=0,DFS2(x); sort(stack+1,stack+top+1); for(j=top,i=1;i<=top;i++) { for(;j&&stack[i].first+stack[j].first>k;j--); for(l=j;k&&stack[i].first+stack[l].first==k;l--) ans[stack[i].second+stack[l].second]+=flag; } } void Tree_Divide_And_Conquer(int root,int size) { int i,cg; Find_Centre_Of_Gravity(root,size,cg); if(fa[cg]) siz[fa[cg]]=size-siz[cg]; DFS1(cg,0,0,0); Calculate(cg,1); for(i=head[cg];i;i=table[i].next) if(!table[i].ban) { table[i].ban=table[i^1].ban=1; Calculate(table[i].to,-1); Tree_Divide_And_Conquer(table[i].to,siz[table[i].to]); } } void Add(int x,int y,int z) { table[++tot].to=y; table[tot].f=z; table[tot].next=head[x]; head[x]=tot; } int main() { int i,x,y,z; cin>>n>>k; for(i=1;i