还有两天就要去FJWC啦…
题意：一颗无根树，$k$为给定常数，求树上距离不超过$k$的点对的数量，多组数据，$n leq 10^4$.
应该是点分治经典题~
一般对于无根树我们都可以把它转变成有根树（其实树上路径不管哪个根都一样嘛），假设我们已经钦定了一个根$rot$（后面会说其实这个根应该是重心），对于$rot$这颗树中的对答案有贡献的路径，要么经过$rot$，要么直接就是$rot$的某一颗子树的答案，这两种情况之间没有交集直接相加，这里就出现了子问题。
而对于经过$rot$的路径的贡献，对可以通过处理一遍$rot$的子树里到它的距离$dis[]$在$O(nlogn)$时间内统计（具体见代码，其实就排个序然后扫描）。这样对于每个点我们只要找根，处理经过$rot$的路径的答案(1)，删除$rot$然后递归对$rot$的所有相邻点$cur$递归的求答案(2)，不过这里出现了重复计算（设$w$为当前点到相邻点$cur$的边的长度）：在(1)当中其实重复计算了$cur$里满足$dis[x]+w+dis[y]+w leq k$的点对多算了，所以我们还要减掉这种答案（你问我怎么减？看代码啦~）
实现删除的时候有个trick就是用一个数组$vis[]$来记录这个点处理过没…处理过了直接不管它。
时间复杂度？假设最多递归了$T$层，计算每一层的答案一定不超过$O(nlogn)$，总复杂度就变成了$O(T*nlogn)$。如果随便钦定某个根递归层数太大的话会被卡成$O(n^2logn)$的，嗯那么要让递归层数小的话当然就选择这个子树的重心啦~每次$O(n)$的算重心，这样$x$的所有子树的大小都不会超过整棵树大小的一半，所以深度就是$(logn)$的了，总复杂度$O(nlog^2 n)$~
呼~
#include<cstdio> #include<cstring> #include<algorithm> #define rep(i,n) for(register int i=1;i<=n;i++) using namespace std; const int N=10005; inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();} while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();} return f?s:-s; } struct edge { int to,nxt,w; edge(int to=0,int nxt=0,int w=0):to(to),nxt(nxt),w(w){} }edges[N<<1]; int n,k,cnt,tot; int head[N<<1],dis[N],size[N],g[N],vis[N]; inline void addEdge(int u,int v,int w) { edges[++cnt]=edge(v,head[u],w); head[u]=cnt; } #define cur edges[i].to inline void dfs_root(int x,int f) { size[x]=1;g[x]=0; for(register int i=head[x];i;i=edges[i].nxt)if(!vis[cur]&&cur!=f) { dfs_root(cur,x);size[x]+=size[cur]; g[x]=max(g[x],size[cur]); } } inline int calc_root(int x,int f,int rot) { int res=0,minx=n; for(register int i=head[x];i;i=edges[i].nxt)if(!vis[cur]&&cur!=f) { int tmp=calc_root(cur,x,rot); if(g[tmp]<minx)minx=g[tmp],res=tmp; } g[x]=max(g[x],size[rot]-size[x]); if(g[x]<minx)minx=g[x],res=x; return res; } inline int get_root(int x) { dfs_root(x,-1); return calc_root(x,-1,x); } inline void dfs_dis(int x,int d,int f) { dis[++tot]=d; for(register int i=head[x];i;i=edges[i].nxt) if(!vis[cur]&&cur!=f)dfs_dis(cur,d+edges[i].w,x); } inline int calc(int x,int w) { tot=0; dfs_dis(x,w,-1);sort(dis+1,dis+tot+1); int j=tot,res=0; for(register int i=1;i<=j;i++) { while(i<j&&dis[i]+dis[j]>k)j--; res+=j-i; }return res; } inline int dfs(int x) { int rot=get_root(x),res=0; vis[rot]=1; res+=calc(rot,0); for(register int i=head[rot];i;i=edges[i].nxt)if(!vis[cur]) { res-=calc(cur,edges[i].w);//算距离的时候多加个变量就行啦 //注意不要把两种合起来写…一个是rot的子树一个是cur的子树 res+=dfs(cur); } return res; } #undef cur int main() { while(scanf("%d%d",&n,&k)==2&&(n+k)) { cnt=0; rep(i,n-1) { int u,v,w;u=read();v=read();w=read(); addEdge(u,v,w);addEdge(v,u,w); } printf("%d ",dfs(1)); rep(i,cnt)head[i]=0;rep(i,n)vis[i]=0; } return 0; }