【题解】

一道点分治模板好题

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

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

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

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

#include
    
     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]