洛谷 P4178 Tree —— 点分治

题目：https://www.luogu.org/problemnew/show/P4178

这道题要把 dep( dis? ) 加入一个 tmp 数组里，排序，计算点对，复杂度很美；

没有写 sort 竟然还有50分！

虽然调了很久不过第一次用对拍找出了错误！

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const maxn=40005,inf=0x3f3f3f3f;
int n,hd[maxn],ct,to[maxn<<1],nxt[maxn<<1],w[maxn<<1],tmp[maxn],l,r;
int sum,siz[maxn],dep[maxn],mx,rt;
ll ans,K;
bool vis[maxn];
void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; w[ct]=z; hd[x]=ct;}
void getrt(int x,int fa)
{
    siz[x]=1; int nmx=0;
    for(int i=hd[x],u;i;i=nxt[i])
    {
        if(to[i]==fa||vis[to[i]])continue;
        getrt(u=to[i],x);
        siz[x]+=siz[u]; nmx=max(nmx,siz[u]);
    }
    nmx=max(nmx,sum-siz[x]);
    if(nmx<mx)mx=nmx,rt=x;
}
void getdep(int x,int fa)
{
    tmp[++r]=dep[x];
    for(int i=hd[x];i;i=nxt[i])
    {
        if(to[i]==fa||vis[to[i]])continue;
        dep[to[i]]=dep[x]+w[i];
        getdep(to[i],x);
    }
}
ll calc(int x,int w)
{
    dep[x]=w; r=0; getdep(x,0);
    l=1; ll ret=0;
    sort(tmp+l,tmp+r+1);//!!!
    while(l<=r)
    {
        if(tmp[l]+tmp[r]<=K)ret+=r-l,l++;//l -> l+1,l+2,...,r
        else r--;
    }
    return ret;
}
void work(int x)
{
    ans+=calc(x,0); vis[x]=1;
    for(int i=hd[x];i;i=nxt[i])
    {
        if(vis[to[i]])continue;
        ans-=calc(to[i],w[i]);
        sum=siz[to[i]]; mx=inf; 
//        getrt(to[i],x);
        getrt(to[i],0);  
        work(rt);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x,y,w;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w); add(y,x,w);
    }
    scanf("%lld",&K);
    sum=n; mx=inf; getrt(1,0); 
    work(rt);
    printf("%lld
",ans);
    return 0;
}