【题解】P4178 Tree

一道点分治模板好题

不知道是不是我见到的题目太少了，为什么这种题目都是暴力开值域的桶QAQ？？

问点对，考虑点分治吧。直接用值域树状数组开下来，统计的时候直接往树状数组里面查询。记得每一层先把这一层的答案统计一下，统计的方法就是刚刚讲的在桶里查。

问题是回溯，值域不大，所以常数还可以，但是我们最好还是开个\(temp\)把我们做修改的地方记录一下，在\(calc\)返回的时候直接回溯。

时间复杂度\(nlog^2n\) 有一些细节需要注意。比如要把\(d[]\)的先统计进去。这一部分答案是从节点到根，没有被点分治覆盖到。

#include<bits/stdc++.h>

using namespace std;

#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)

#define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)

#define Max(a,b) ((a)<(b)?(b):(a))

#define Min(a,b) ((a)<(b)?(a):(b))

#define midd register int mid=(l+r)>>1

#define TMP template < class ccf >

#define lowbit(x) ((x)&(-x))

TMP inline ccf qr(ccf b){

    char c=getchar();

    int q=1;

    ccf x=0;

    while(c<48||c>57)

	q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)

	x=x*10+c-48,c=getchar();

    return q==-1?-x:x;

}

const int maxn=40000+15;

int n,m;

struct E{

    int to,w,nx;

}e[maxn<<1];

int head[maxn];

int cnt;

inline void add(int fr,int to,int w,bool f){

    e[++cnt]=(E){to,w,head[fr]};

    head[fr]=cnt;

    if(f)

	add(to,fr,w,0);

}

bool usd[maxn];

int siz[maxn];

int spa[maxn];

int sav[maxn];

int d[maxn];

int rt;

int k;

int data[20005];

int q[maxn];

int sum;

int ans;

inline void add(int x,int qaq){

    for(register int t=x+1;t<=20001;t+=lowbit(t))data[t]+=qaq;

}

inline int ask(int x){register int ret=0;

    for(register int t=Min(x+1,20001);t>0;t-=lowbit(t))ret+=data[t];

    return ret;

}

void dfsroot(int now,int last){

    siz[now]=1;

    spa[now]=0;

    ERP(t,now){

	if(e[t].to!=last&&!usd[e[t].to]){

	    dfsroot(e[t].to,now);

	    siz[now]+=siz[e[t].to];

	    spa[now]=Max(spa[now],siz[e[t].to]);

	}

    }

    spa[now]=Max(spa[now],sum-siz[now]);

    if(spa[now]<spa[rt]||rt==0)

	rt=now;

}

void dfsdis(int now,int last,int ew){

    d[now]=d[last]+ew;

    sav[++sav[0]]=d[now];

    ERP(t,now){

	if(e[t].to!=last&&!usd[e[t].to]){

	    dfsdis(e[t].to,now,e[t].w);

	}

    }

}

inline void calc(int now){

    register int p=0;

    ERP(t,now){

	if(!usd[e[t].to]){

	    sav[0]=0;

	    dfsdis(e[t].to,0,e[t].w);

	    RP(i,1,sav[0])

		ans+=ask(k-sav[i]);

	    RP(i,1,sav[0])

		if(sav[i]<=k) ans++;

	    RP(i,1,sav[0]) add(sav[i],1);

	    RP(i,1,sav[0]) q[++p]=sav[i];

	}

    }

    RP(t,1,p)

	add(q[t],-1);

}

void solve(int now){

    usd[now]=1;

    calc(now);

    ERP(t,now){

	if(!usd[e[t].to]){

	    sum=siz[e[t].to];

	    rt=0;

	    dfsroot(e[t].to,0);

	    solve(rt);

	}

    }

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    n=qr(1);

    for(register int t=1,t1,t2,t3;t<n;++t){

	t1=qr(1);

	t2=qr(1);

	t3=qr(1);

	add(t1,t2,t3,1);

    }

    k=qr(1);

    sum=n;

    dfsroot(1,0);

    solve(rt);

    cout<<ans<<endl;

    return 0;

}