题目描述：
T64有一个好朋友，叫T128。T128是寄宿生，并且最近被老师叫过去当宿管了。宿管可不是一件很好做的工作，碰
巧T128有一个工作上的问题想请T64帮忙解决。T128的寝室条件不是很好，所以没有很多钱来装修。礼间寝室仅由n
-1条双向道路连接，而且任意两间寝室之间都可以互达。最近，T128被要求对一条路径上的所有寝室进行管理，这
条路径不会重复经过某个点或某条边。但他不记得是哪条路径了。他只记得这条路径上有不少于k个寝室。于是，
他想请T64帮忙数一下，有多少条这样的路径满足条件。嗯…还有一个问题。由于最近有一些熊孩子不准晚上讲话
很不爽，他们决定修筑一条“情报通道”，如果通道建成，寝室就变成了一个N个点N条边的无向图。并且，经过“
情报通道”的路径也是合法的。T128心想：通道建成之前，T64还有一个高效的算法帮我数路径条数，但是通道建
成之后，他还有办法吗？对，T64手忙脚乱，根本数不清有多少条路径。于是他找到了你
算法标签：点分治
思路：
当m==n-1时是裸的点分治，考虑再加一条边，统计对答案的贡献，对于加边后构成的环，依此枚举断掉每一条边的贡献，怎么断不会算重的问题看代码吧。以下代码：
#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=1e5+5;struct node{int l,r;}P;bool vis[N],tag[N];LL ans; int n,m,head[N],ne[N<<1],to[N<<1],cnt,fa[N],son[N],sz[N],size,A[N],f[N],tot,B[N],nt,rt,k,bef[N],dis[N],way[N]; il int read(){int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;} il void insert(int x,int y){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;} il int getfa(int x){if(!fa[x])return x;return fa[x]=getfa(fa[x]);} il int query(int x){int res=0;for(;x;x-=x&-x)res+=f[x];return res;} il void ins(int x,int v){for(;x<=n;x+=x&-x)f[x]+=v;} il void getrt(int x,int fa){ son[x]=0;sz[x]=1; for(int i=head[x];i;i=ne[i]){ if(fa==to[i]||vis[to[i]])continue; getrt(to[i],x);sz[x]+=sz[to[i]]; if(sz[to[i]]>son[x])son[x]=sz[to[i]]; } son[x]=max(son[x],size-sz[x]);if(son[x]<son[rt])rt=x; } il void getval(int x,int fa,int dep){ A[++tot]=dep+1;ans+=query(n)-query(max(k-dep-1,0)); for(int i=head[x];i;i=ne[i])if(fa!=to[i]&&!vis[to[i]])getval(to[i],x,dep+1); } il void solve(int x){ vis[x]=1;B[nt=1]=1;ins(1,1); for(int i=head[x];i;i=ne[i]){ if(vis[to[i]])continue; tot=0;getval(to[i],x,1); for(int i=1;i<=tot;i++)ins(A[i],1),B[++nt]=A[i]; } for(int i=1;i<=nt;i++)ins(B[i],-1); for(int i=head[x];i;i=ne[i]){ if(vis[to[i]])continue; rt=0;size=sz[to[i]];getrt(to[i],x); solve(rt); } } il void dfs1(int x,int fa,int dep){ bef[x]=fa;ins(dis[x]=dep,1); for(int i=head[x];i;i=ne[i])if(fa!=to[i])dfs1(to[i],x,dep+1); } il void del(int x,int fa){ ins(dis[x],-1); for(int i=head[x];i;i=ne[i])if(!tag[to[i]]&&fa!=to[i])del(to[i],x); } il void cal(int x,int fa,int dep){ ans+=query(n)-query(max(0,k-dep-1)); for(int i=head[x];i;i=ne[i])if(!tag[to[i]]&&fa!=to[i])cal(to[i],x,dep+1); } int main() { n=read();m=read();k=read(); if(m==n-1){ for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);} } else{ for(int i=1;i<=n;i++){ int l=read(),r=read(); int x=getfa(l),y=getfa(r); if(x==y)P=(node){l,r}; else fa[x]=y,insert(l,r),insert(r,l); } } son[0]=n;rt=0;size=n;getrt(1,0);solve(rt); if(m==n){ dfs1(P.l,0,1);tot=0; for(int i=P.r;i;i=bef[i])tag[way[++tot]=i]=1; for(int i=1;i<tot;i++)del(way[i],0),cal(way[i],0,i); } printf("%lld ",ans); return 0; }