Luogu

算法

点分治裸题。

先考虑暴力做法。在【模板】点分治1的基础上从1到k循环统计一遍答案即可。

考虑对暴力做优化。发现算法的主要瓶颈在calc函数内，我们考虑把它从$O(n^2)$降至$O(n\ \log\ n)$。

直接排序然后 $\mathrm{two-pointers}$ 即可。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,k;

//邻接表 
struct Edge { int v,w,nxt; } e[80010];
int head[40010],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v; e[cnt].w=w;
    e[cnt].nxt=head[u]; head[u]=cnt;
}

//求重心 
int root,sum;
int f[40010],sz[40010];
bool vis[40010];

inline void getroot(int u,int fa) {
    sz[u]=1; f[u]=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==fa||vis[v]) continue;
        getroot(v,u); sz[u]+=sz[v];
        f[u]=max(f[u],sz[v]);
    }
    f[u]=max(f[u],sum-sz[u]);
    if (f[u]<f[root]) root=u;
}

int o[40010],dep[40010];

//求深度 
inline void getdeep(int u,int fa) {
    o[++cnt]=dep[u];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (v==fa||vis[v]) continue;
        dep[v]=dep[u]+w;
        getdeep(v,u);
    }
}

int ans;

//点分治
inline int calc(int u,int d0) {
    cnt=0; dep[u]=d0; getdeep(u,0);
    sort(o+1,o+cnt+1);
    int i=1,j=cnt,rt=0;
    while (i<j) {
        if (o[i]+o[j]<=k) rt+=j-i,i++;
        else j--;
    }
    return rt;
}
inline void solve(int u) {
    ans+=calc(u,0); vis[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (vis[v]) continue;
        ans-=calc(v,w);
        sum=sz[v],root=0;
        getroot(v,0);
        solve(root);
    }
}

int main() {
    n=read();
    for (re int i=1;i<n;i++) {
        int a=read(),b=read(),c=read();
        addEdge(a,b,c);
        addEdge(b,a,c);
    }
    k=read();
    sum=f[0]=n;
    getroot(1,0);
    solve(root);
    printf("%d\n",ans);
    return 0;
}