POJ1741（点分治）

传送门

点分治模板题

大概意思就是从树的重心开始走，每次计算所有到当前根节点距离大于k的数的和

然后减去每颗子树中距离大于k的数的数量

然后再递归到每颗子树中去求解

#include<algorithm>
#include<cmath>
#include<cstring>
#include<string.h>
#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<cstdlib>
using namespace std;
inline int read(){
    char ch=getchar();
    int res=0,f=1;
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res*f;
}
int n,k,fa[10005],maxn,siz[10004],son[10004],dis[10005],cnt,root,adj[10005],nxt[20005],to[20005],val[20005];
bool vis[10005];
#define ll long long
ll ans;
inline void addedge(int u,int v,int w){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
    nxt[++cnt]=adj[v],adj[v]=cnt,to[cnt]=u,val[cnt]=w;
}
inline void getroot(int u,int fa)
{
    siz[u]=1; son[u]=0;
    for(int e=adj[u];e;e=nxt[e])
    {
        int v=to[e];
        if (v!=fa&&!vis[v])
        {
            getroot(v,u);
            siz[u]+=siz[v];
            son[u]=max(son[u],siz[v]);
        }
    }
    son[u]=max(son[u],maxn-siz[u]);
    if (son[u]<son[root]) root=u;
}
int d[10005],ecnt;
inline void getdist(int u,int fa){
    d[++ecnt]=dis[u];
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(!vis[v]&&v!=fa){
            dis[v]=dis[u]+val[e];
            getdist(v,u);    
        }
    }
}
inline int calc(int u,int lenth){
    dis[u]=lenth;
    ecnt=0;
    getdist(u,0);
    sort(d+1,d+ecnt+1);
    int l=1,r=ecnt,num=0;
    while(l<r){
        if(d[l]+d[r]<=k)num+=r-l,l++;
        else r--;
    }
    return num;
}
inline void solve(int u){
    vis[u]=true;
    ans+=calc(u,0);
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(vis[v])continue;
        ans-=calc(v,val[e]);
        maxn=siz[v];
        getroot(v,root=0);
        solve(root);
    }
}
int main(){
    n=read(),k=read();
    while(n!=0&&k!=0){
        memset(adj,0,sizeof(adj));
        memset(vis,0,sizeof(vis));
        cnt=0,ans=0;
        for(int i=1;i<n;i++){
            int u=read(),v=read(),w=read();
            addedge(u,v,w);
        }
        son[0]=maxn=n;
        getroot(1,root=0);
        solve(root);
        cout<<ans<<'
';
        n=read(),k=read();
    }
}