本文共 3021 字，大约阅读时间需要 10 分钟。

5 41 2 31 3 11 4 23 5 10 0

8

论文题：

题意：

题解

参考博客：

每次分治，我们首先算出重心，为了计算重心，需要进行两次dfs，第一次把以每个结点为根的子树大小求出来，第二次是从这些结点中找重心

找到重心后，需要统计所有结点到重心的距离，看其中有多少对小于等于K，这里采用的方法就是把所有的距离存在一个数组里，进行快速排序，这是nlogn的，然后用一个经典的相向搜索O(n)时间内解决。但是这些求出来满足小于等于K的里面只有那些路径经过重心的点对才是有效的，也就是说在同一颗子树上的肯定不算数的，所以对每颗子树，把子树内部的满足条件的点对减去。

最后的复杂度是n logn logn    其中每次快排是nlogn 而递归的深度为logn

注意这里求重心和以往不同，因为每次分治都要对一棵子树求重心，所以这棵树的大小不定，所以要两次dfs。详细操作见代码。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef long long ll;typedef pair
            
              PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=10000+100;int head[maxn],vis[maxn],dis[maxn];struct edge{ int to,next,w;}e[maxn*2]; //int tol=0;void add(int u,int v,int w){ e[++tol].to=v,e[tol].next=head[u],e[tol].w=w,head[u]=tol;}int root,mi,num;int mx[maxn];int ans=0;int n,k;int tn;int sz[maxn];void dfssize(int u,int f) //处理子树大小{ sz[u]=1;mx[u]=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v==f||vis[v]) continue; dfssize(v,u); sz[u]+=sz[v]; if(sz[v]>mx[u]) mx[u]=sz[u]; }}void dfsroot(int r,int u,int f) //求重心{ if(sz[r]-sz[u]>mx[u]) mx[u]=sz[r]-sz[u]; if(mi>mx[u]) { mi=mx[u]; root=u; } for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(vis[v]||v==f) continue; dfsroot(r,v,u); }}void getdis(int u,int f,int d)//求距离{ dis[num++]=d; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(vis[v]||v==f) continue; getdis(v,u,d+e[i].w); }}int cal(int u,int d){ int res=0; num=0; getdis(u,-1,d); sort(dis,dis+num); int i=0,j=num-1; while(i
             
              k) j--; res+=j-i; i++; } return res;}void dfs(int u){ mi=inf; dfssize(u,-1); //这一步和下面的一步求出重心 dfsroot(u,u,-1); ans+=cal(root,0); vis[root]=1; //将这个根处理完后打上标记“去掉” for(int i=head[root];i;i=e[i].next) { int v=e[i].to; if(vis[v]) continue; ans-=cal(v,e[i].w); dfs(v); }}int main(){ while(~scanf("%d%d",&n,&k)) { if(n==0&&k==0) break; tol=0;ans=0; memset(head,0,sizeof(head)); memset(sz,0,sizeof(sz)); memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); rep(i,1,n) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w),add(v,u,w); } dfs(1); printf("%d\n",ans); } return 0;}
             
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/fouzhe/article/details/55258714 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！