题目链接：

---

给出一个$n$个点的树，树上每一个点都有一个值$age$,每条边都有边权，每次查询一个点，求出树中所有点上权值${L<=age[i]<=R}$的点到它的距离的和。

---

为了学习传说中的动态树分治，我就把这个题当作模板题来写了。

当然这题也可以。

 

　　为什么叫做动态树分治？其实就是把分治的结构记录了下来，树分治的好处在于每一次操作(找出当前块重心并再次递归)可以快速减少树的大小，我们记录下这个每次求出的树的重心的结构，这样的分治结构是严格log层的，每一次查询的是沿着分治结构构出的树往上跳，统计所有点到当前点的距离(这里需要数据结构维护，可以开一个vector动态记录每一个点在分治中所管辖的子树的所有点的信息，然后查询的时候二分即可)，然后再往分治结构构成的树的父亲上跳，因为在分治结构的父亲所管辖的子树一定包含了当前点所管辖的子树，所以需要容斥(全是细节)。复杂度${O(nlog^{2})}$

　　可怕的是BZOJ上似乎卡常？

 

 

 

---

code:

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 using namespace std; 10 #define maxn 600100 11 #define llg long long 12 #define RG register llg 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 14 llg Q,A,n,m,age[maxn],ans,dad[maxn],dadv[maxn],maxage,f[maxn][21],dis[maxn][21],deep[maxn]; 15 bool bj[maxn],bj_[maxn]; 16 llg g[maxn<<1],maxl,weizhi,dl[maxn],tail,L,R,o,te,buf[50]; 17 18 inline void write(RG x) 19 { 20 if (x<0) putchar('-'),x=-x; 21 buf[0]=0; 22 while (x) buf[++buf[0]]=x%10,x/=10; 23 if (!buf[0]) buf[0]=1,buf[1]=0; 24 while (buf[0]) putchar('0'+buf[buf[0]--]); 25 putchar('\n'); 26 } 27 28 inline llg getint() 29 { 30 llg w=0,q=0; 31 char c=getchar(); 32 while((c<'0' || c>'9') && c!='-') c=getchar(); 33 if (c=='-') q=1, c=getchar(); 34 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); 35 return q ? -w : w; 36 } 37 38 struct edge{ 39 int y,next; 40 llg d; 41 }e[maxn<<1]; 42 43 void addedge(RG x,RG y,RG d){ 44 e[++te].y=y; 45 e[te].d=d; 46 e[te].next=g[x]; 47 g[x]=te; 48 } 49 50 struct node 51 { 52 llg age,dis,qz,qz_,dis_; 53 }; 54 inline bool cmp(const node&a,const node&b) { return a.age
             
              c[maxn]; 57 58 inline void clear_() { for (RG i=1;i<=tail;i++) bj_[dl[i]]=0; tail=0;} 59 60 inline void dfs(RG x,RG fa) 61 { 62 for (RG i=g[x];i;i=e[i].next) 63 { 64 RG v=e[i].y; 65 if (v==fa) continue; 66 f[v][0]=x; dis[v][0]=e[i].d; 67 deep[v]=deep[x]+1; 68 dfs(v,x); 69 } 70 } 71 72 inline void make_f() 73 { 74 for (RG j=1;j<=17;j++) 75 for (RG i=1;i<=n;i++) 76 { 77 f[i][j]=f[f[i][j-1]][j-1]; 78 dis[i][j]=dis[i][j-1]+dis[f[i][j-1]][j-1]; 79 } 80 } 81 82 inline llg find_dis(RG x,RG y) 83 { 84 if (x==0 || y==0) return 0; 85 RG ans=0; 86 if (deep[x]
              
               =0;i--) 88 if (deep[f[x][i]]>=deep[y]) 89 { 90 ans+=dis[x][i]; 91 x=f[x][i]; 92 } 93 if (x==y) return ans; 94 for (RG i=17;i>=0;i--) 95 if (f[x][i]!=f[y][i]) 96 { 97 ans+=dis[x][i]+dis[y][i]; 98 x=f[x][i],y=f[y][i]; 99 }100 return ans+dis[x][0]+dis[y][0];101 }102 103 void init()104 {105 RG x,y,z;106 cin>>n>>Q>>A;107 for (RG i=1;i<=n;i++) age[i]=getint(),maxage=max(maxage,age[i]);108 for (RG i=1;i
               
                >1;213 if (c[x][mid].age<=V) {wz=mid; l=mid+1;}else{r=mid-1;}214 }215 if (wz==-1) return 0;216 if (pd) return c[x][wz].qz+(dis_-find_dis(dad[x],o))*(wz+1)-c[x][wz].qz_;217 else return c[x][wz].qz_+(wz+1)*(find_dis(dad[x],o)-dis_)-c[x][wz].qz;218 }219 220 inline llg erfen_(RG x,RG V)221 { 222 RG l=0,r=c[x].size()-1,mid,wz=-1;223 while (l<=r)224 {225 mid=(l+r)>>1;226 if (c[x][mid].age<=V) {wz=mid; l=mid+1;}else{r=mid-1;}227 }228 if (wz==-1) return 0;229 return (wz+1)*find_dis(dad[x],o)+c[x][wz].qz_;230 }231 232 inline void find(register llg x)233 {234 RG dis_=find_dis(x,o);235 // llg sum=erfen(x,R,dis_)-erfen(x,L-1,dis_);236 // llg dec=erfen_(x,R)-erfen_(x,L-1);237 ans+=erfen(x,R,dis_,1)+erfen(x,L-1,dis_,0);238 // ans+=sum-dec;239 if (dad[x]!=0) find(dad[x]);240 }241 242 llg dg(llg x)243 {244 if (dad[x]!=0) return dg(dad[x])+1;245 else return 1;246 }247 248 int main()249 {250 yyj("shop");251 init();252 solve(1,0);253 /* for (llg i=1;i<=n;i++) 254 {255 maxl=max(maxl,dg(i));256 }257 cout<