黄昏夕阳，铺一片余晖锦缎，远处炊烟袅袅，我们活在这美好温暖的人间。
本文是基于辰星凌的博客QAQ大佬的博客的自己的一些“摘抄”和自己的一些想法
点分治的核心思想在于依据重心划分子连通块，按照分治递归的顺序提一颗新树出来，对于每一个找到的重心，将上一层分治时的重心设为它的父亲，得到一颗大小不变、最多 logn 层的重构树
「HNOI2015」开店
维护一颗带点权、边权树，每次给出 \(x,l,r\)，查询 \(∑_{l⩽Ay⩽r}dis(x,y)\)，其中 \(Ay\) 为 \(y\) 的点权。
\(f1(i,j)=∑_{x∈subtree(i),Ax⩽j}dis(x,i)\)
\(f2(i,j)=∑_{x∈subtree(i),Ax⩽j}dis(x,fai)\)
\(sz(i,j)=∑_{x∈subtree(i),Ax⩽j}1\)
\(G(i,fa_i)= f1(fa_i,k-dis(x,fa_i))−f2(i,k-dis(x,fa_i))+dis(x,fa_i)×(sz(fa_i,k)−sz(i,k))\)
\(f1\)多计算了\(i\)子树内部的，所以减去\(f2\) \(i\)子树内部据\(fa_i\)满足\(f1\)条件的（也就是多算的）
总答案=\(fa_i-i\)子树下距\(fa_i\)小于等于\(k-dis(x,fa_i)\)的+\(dis(x,fa_i)\times\)满足条件点的个数
\(ans(x,k)=f1(x,k)+∑_{i∈fatree(x),fa_i≠0}G(i,fa_i)\)
void solve(ll u){
dfs1(u);//get size
if(sz[u]==1){
cut[u]=1;
fa[u].push_back({u,0,-1});
return;
}//边界条件
Size=sz[u],mn=INF;
dfs2(u);//找 重心
cut[Rt]=1;//重心已经被删掉
fa[Rt].push_back({Rt,0,-1});
for(ll i=hd[Rt],t=0;i;i=nxt[i]){
ll y=to[i];
if(cut[y])continue;//之前已经作为重心被使用过了
d[y]=val[i];
dfs3(y,Rt,t);//预处理vector
son[Rt][t].push_back({INF,0,0});//
sort(son[Rt][t].begin(),son[Rt][t].end());//按点权排序
for(ll j=son[Rt][t].size()-2;j>=0;j--){
son[Rt][t][j].sz+=son[Rt][t][j+1].sz;//处理后缀和
son[Rt][t][j].dis+=son[Rt][t][j+1].dis;
}
t++;
}
for(ll i=hd[Rt];i;i=nxt[i]){
ll y=to[i];
if(!cut[y])solve(y);
}//递归点分治
}
「BZOJ3730」震波
以下用 \(fa_i\) 表示点 \(i\) 在虚树上的父亲，\(subtree(i)\) 为点 \(i\) 在虚树上的子树集合，\(fatree(i)\) 为点 \(i\) 在虚树上的祖先集合，\(dis(i,j)\) 为 \(i,j\) 两点在原树上的距离，\(Ai\) 为点 \(i\) 的点权。
\(f1(i,j)=∑_{x∈subtree(i),dis(x,i)⩽j}Ax\)
即虚树上 i 的子树中与 i 距离小于等于 j 的点权值之和
\(f2(i,j)=∑_{x∈subtree(i),dis(x,fai)⩽j}Ax\)
即虚树上 i 的子树中与 \(fa_i\) 距离小于等于 \(j\) 的点权值之和
在一次查询 \((x,k)\) 中，对于虚树上的一对父子节点 \((i,fa_i)\)，\(subtree(fa_i)−subtree(i)\) 对答案的贡献为 \(G(i,fa_i)=f1(fa_i,k−dis(x,fa_i))-f2(i,k−dis(x,fa_i)) \)
\(f1(fa_i,k−dis(x,fa_i))\)包含了多余的i子树的部分
因此后面减去\(f2(i,k−dis(x,fa_i))\) i子树小于等于k−dis(x,fa_i)的部分
\(ans(x,k)=f1(x,k)+ ∑_{i∈fatree(x),fa_i≠0}G(i,fa_i)\)
注意前面那个 \(f1(x,k)\)是因为容斥求和后没有被统计进去，所以要单独算
有一个问题就是：
void solve(int x,int F){//处理重心x所囊括的连通块
int now=Size;
vis[x]=1;
fa[x]=F;
f1[x].build(now/2+1);
f2[x].build(now+1);//这个地方大小为什么是now？为什么不是now/2？
for(int i=hd[x];i;i=a[i].nxt){
int y=a[i].to;
if(vis[y]) continue;
Size=sz[y]>sz[x]?now-sz[x]:sz[y];//注意子连通块大小不要直接用sz[y]
rt=0;
mx[rt]=INF;
getrt(y,0);
solve(rt,x);
}
}
\(Attention\)：
在 \(subtree(i)\) 中为重心所以 \(f1(i,j)\) 中 \(j\) 的值域为 \([0∼now/2]\)
\(f2(i,j)\) 中 \(j\) 的值域为 \([1∼now]\)
[2010国家集训队]Crash的旅游计划
就是和上面那道题差不多了啦~（呕