P4178 Tree（点分治）

点分治模板题，一般用于树上路径统计

点分治基本套路：

将信息化为通过根节点以及在子树中的信息

这样使用一个solve来表示通过根节点的

之后将根节点vis==1递归子树

因为一般来说是无根树，并且为了保证有log层，因此子树中的信息通过寻找重心来做

每次统计完通过根节点后，需要重新计算sz信息，因为子树中根不定。

对于数据较小的，使用树状数组等，否则需要用平衡树，切记不可memset

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6e5+10;
int n;
int root;
int h[N],ne[N],e[N],w[N],idx;
int d[N],cnt;
int vis[N];
int K;
int tr[N];
int sz[N];
int lowbit(int x){
    return x&(-x);
}
void change(int x,int c){
    int i;
    for(i=x;i<=K;i+=lowbit(i)){
        tr[i]+=c;
    }

}
int sum(int x){
    int i;
    int res=0;
    for(i=x;i;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int u,int fa,int tot){
    sz[u]=1;
    int i;
    int ans=0;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa||vis[j])
            continue;
        dfs(j,u,tot);
        sz[u]+=sz[j];
        ans=max(ans,sz[j]);
    }
    ans=max(ans,tot-sz[u]);
    if(ans*2<=tot)
        root=u;
}
void dfs_sz(int u,int fa){
    int i;
    sz[u]=1;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa||vis[j])
            continue;
        dfs_sz(j,u);
        sz[u]+=sz[j];
    }
}
void dfs_dis(int u,int fa,int dis){
    d[++cnt]=dis;
    int i;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa||vis[j])
            continue;
        dfs_dis(j,u,dis+w[i]);
    }
}
void dfs_clear(int u,int fa,int dis){
    if(dis)
        change(dis,-1);
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa||vis[j])
            continue;
        dfs_clear(j,u,dis+w[i]);
    }
}
int work(int u,int tot){
    dfs(u,-1,tot);
    u=root;
    int i;
    int res=0;
    vis[u]=1;
    dfs_sz(u,-1);
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(vis[j])
            continue;
        cnt=0;
        dfs_dis(j,u,w[i]);
        for(int k=1;k<=cnt;k++){
            if(d[k]<=K)
                res++;
            res+=sum(max(0,K-d[k]));
        }
        for(int k=1;k<=cnt;k++){
            change(d[k],1);
        }

    }

    dfs_clear(u,-1,0);
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(vis[j])
            continue;
        res+=work(j,sz[j]);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int i;
    memset(h,-1,sizeof h);
    for(i=1;i<n;i++){
        int u,v,c;
        cin>>u>>v>>c;
        add(u,v,c);
        add(v,u,c);
    }
    cin>>K;
    cout<<work(1,n)<<endl;
}