点分治模板题。

男人必做八题。

每棵子树统计经过根节点的满足情况个数，再减去子树中不经过根节点的情况个数，类似于一个容斥。复杂度O（Nlog^2N）

注意每次getroot所定的树的大小是改变的，不能一直是n否则会退化。

By：大奕哥

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int N=10005; 8 struct node 9 {10     int to,nex,w;11 }e[N<<1];12 int head[N],f[N],cnt,v[N],s[N],d[N],n,k,rt,num,ans,maxn;13 void add(int x,int y,int w)14 {15     e[++cnt].to=y;e[cnt].w=w;e[cnt].nex=head[x];head[x]=cnt;16 }17 void getrt(int x,int fa)18 {19     s[x]=1;f[x]=0;20     for(int i=head[x];i;i=e[i].nex)21     {22         int y=e[i].to;23         if(y==fa||v[y])continue;24         getrt(y,x);s[x]+=s[y];25         f[x]=max(f[x],s[y]);26     }27     f[x]=max(f[x],maxn-s[x]);28     if(f[x]
          
           k)--j;49 pre+=j-i;50 }51 return pre;52 }53 void dfs(int x)54 {55 v[x]=1;ans+=calc(x,0);56 for(int i=head[rt];i;i=e[i].nex)57 {58 int y=e[i].to;59 if(!v[y])60 {61 ans-=calc(y,e[i].w);62 rt=0,maxn=s[y];getrt(y,0);63 dfs(rt);64 }65 }66 }67 int main()68 {69 while(~scanf("%d%d",&n,&k))70 {71 if(!n&&!k)break;72 int x,y,w;73 memset(head,0,sizeof(head));cnt=0;74 memset(v,0,sizeof(v));ans=0;75 for(int i=1;i