点分治
题目让我们找是否存在距离为 $k$ 的点对是否存在。如果暴力统计每个点对之间的距离，时间显然会爆。
在我们暴力找的时候，是乱序的，所以我们首先要让它有序。首先，我们先要找到最小值，可以找树的重心，这样会快就能找到最短的边，然后将重心标记换一个近似于重心的点，找次短……但是这样的复杂度仍然暴力。
我们要找的是是否存在，所以完全可以在找到最短或其它的时候往两边扩展，查看是否会产生结果，我们找的最短，次短……只是一个遍历的顺序。
找到最大范围，通过不断比对大小，一点点往里缩，尝试匹配即可。
代码思路
连边（读取基础信息）。
存储询问（找到一个根节点后，根据每个询问尝试匹配每种情况）。
找重心（处理子树的重量，判断重心）。
标记重心标号（后边换重心是方方便确认是否已经遍历过）。
二分，处理长度，尝试匹配，匹配成功标记。
换重心，继续尝试。
按标记，输出结果。
（每个节点只能记录当时没有被标记过当过重心的节点，所以每个节点的子树的重量（子树中的节点的个数）不同。）
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cctype>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e6+10;
int n,m;
int q_i[o_o];//存储询问
int m_s[o_o];
//存储最大树（最大子树或除了最大子树之外的部分）
//如果两者相差很小，说明以它为根节点更平衡
int s_z[o_o];//存储子树大小
int g_g;//根节点（重心）
int x_a;//临时数组的下标
int d_p[o_o];//深度（到根节点权值）
int b_i[o_o];//记录当前节点从哪个节点来的
int a_i[o_o];//临时数组
bool b_p[o_o];//判断是否标记过
bool b_b[o_o];//统计结果
struct po{//链式前向星
int v;
int n_t;
int v_l;
}p_p[o_o<<1];
int h_d[o_o],x_p;
void a_d(int u,int v,int w){//加边
x_p++;
p_p[x_p].n_t=h_d[u];
p_p[x_p].v=v;
p_p[x_p].v_l=w;
h_d[u]=x_p;
}
void g_t(int k,int f,int v_l){
s_z[k]=1;//初始化节点大小
m_s[k]=0;//初始化节点最大子树
for(int i=h_d[k];i;i=p_p[i].n_t){//跑边
int v=p_p[i].v;
if(v==f||b_p[v])continue;//是父节点或已经当过根节点了
g_t(v,k,v_l);//继续找
s_z[k]+=s_z[v];//累计子树大小
m_s[k]=max(s_z[v],m_s[k]);//找最大子树
}
m_s[k]=max(m_s[k],v_l-s_z[k]);//选择子树或除了子树
if(!g_g||m_s[k]<m_s[g_g])g_g=k;
//根节点不存在或者比根节点的最大树小，更新根节点
}
bool cmp(int x,int y){//判断深度，保证从小到大
return d_p[x]<d_p[y];
}
void g_l(int k,int f,int l_n,int f_m){
a_i[++x_a]=k;//读取编号
d_p[k]=l_n;//记录深度
b_i[k]=f_m;//记录来的节点（从那个到根节点）
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(v==f||b_p[v])continue;
g_l(v,k,l_n+p_p[i].v_l,f_m);//注意深度累计
//此处的深度就是价值（边权）
}
}
void c_c(int k){
x_a=0;//初始化临时数组下表
a_i[++x_a]=k;//读入当前标号
d_p[k]=0;//初始化根节点的深度
b_i[k]=k;//初始化当前节点到当前节点
for(int i=h_d[k];i;i=p_p[i].n_t){//枚举边
int v=p_p[i].v;
if(b_p[v])continue;
g_l(v,k,p_p[i].v_l,v);
//处理所有节点的基础信息
}
sort(a_i+1,a_i+x_a+1,cmp);//将目前的节点按深度从小到大排序（方便二分）
for(int i=1;i<=m;i++){//处理每个询问
int l=1,r=x_a;//初始化左右边界
if(b_b[i])continue;//已经匹配成功
while(l<r){//暴力找左右长度
if(d_p[a_i[l]]+d_p[a_i[r]]>q_i[i])r--;//比目标大，右边回缩
else if(d_p[a_i[l]]+d_p[a_i[r]]<q_i[i])l++;//比目标小，左边回缩
else if(b_i[a_i[l]]==b_i[a_i[r]]){//来的点相同（根节点做左右）
if(d_p[a_i[r]]==d_p[a_i[r-1]])r--;//如果权值相同，右边回缩
else l++;//否则左边回缩
}else{
b_b[i]=1;//标记，匹配成功
break;
}
}
}
}
void s_v(int k){//处理根节点
b_p[k]=1;//标记
c_c(k);
for(int i=h_d[k];i;i=p_p[i].n_t){//遍历每个边
int v=p_p[i].v;//通向的边
if(b_p[v])continue;
g_g=0;//根节点初始化
g_t(v,0,s_z[v]);
//处理新的重心，在真正重心直接子叶（近似中心）的子树寻找新的重心。
s_v(g_g);//继续处理
}
}
int main(){
n=r_r(),m=r_r();
for(int i=1;i<=n-1;i++){//加边
int u=r_r(),v=r_r(),w=r_r();
a_d(u,v,w);
a_d(v,u,w);
}
for(int i=1;i<=m;i++){
q_i[i]=r_r();//存储询问
if(!q_i[i])b_b[i]=1;//标记询问为 0 的询问
}
m_s[0]=n;//初始化
g_t(1,0,n);//确定根节点
s_v(g_g);//处理根节点
for(int i=1;i<=m;i++){//输出结果
if(b_b[i])puts("AYE");
else puts("NAY");
}
return 0;
}
点分树
题目要我们求点覆盖的权值和单点修改。
和点分治的思路相同的是要找重心，要存节点来源（下面叫做父节点），在上面的题中我们确定的是长度是否存在。但是本题我们求的是范围点值和。
不难发现，我们是根据离点的距离确定范围，那么我们就可以通过存储每个深度（到当前节点的距离）来处理权值和（这里我们用的是 树状数组）。
同时我们要存储当前节点的父节点的深度的权值信息，这样我们就能在从当前节点往回爬的时候更方便的去重。
代码思路
初始化并读取基本信息（节点权值和连边）。
找重心。
处理所有节点到重心的距离，深度贡献的权值。统计处理父节点相关情况。
找新重心，继续处理上边的步骤。
覆盖权值询问。
统计当前节点的贡献。
跳父节点们继续处理贡献同时去重（有些权值贡献多次），结束条件是父节点到节点的距离在覆盖范围内。
输出统计结果，同时记录结果（信息解密要用）。
单点修改。
从当前节点往根节点跳（只对这些点有贡献），树状数组单点修改，接的同时处理记录父节点情况。
城市权值修改。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cctype>
#include<map>
#include<vector>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=2e5+5;
int l_t(int x){
return x&(-x);
}
int n,m;
int a_s;//结果
int l_a;//上次输出，用于解密
int f[o_o];
int d[o_o];
int b_b[o_o];//标记节点是否当过重心
int d_p[o_o];//记录当前重心下每个节点的深度
int m_d_p;//记录当前重心形成的树的最大深度
//链式前向星存边
struct po{
int v;
int n_t;
}p_p[o_o<<1];//存边
int x_p,h_d[o_o];
int v_v[o_o];//每个节点（城市）的权值
map<int,int>i_d[o_o];//记录每个节点在不同重心时的深度
vector<int>l_s[o_o];//当前重心时上次重心的区间和
vector<int>n_s[o_o];//当前重心时的区间权值和
void a_d(int u,int v){//连边
p_p[++x_p].v=v;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
int g_g;//根节点（重心）
int s_n;
int m_s[o_o];//当前节点最大子树
int s_z[o_o];//子树大小
void d_f(int x,int f_a){//找根节点
s_z[x]=1;//初始化子树大小
m_s[x]=0;//初始化当前节点最大子树
for(int i=h_d[x];i;i=p_p[i].n_t){//遍历边
if(p_p[i].v!=f_a&&!b_b[p_p[i].v]){
d_f(p_p[i].v,x);
s_z[x]+=s_z[p_p[i].v];//累计子树大小
m_s[x]=max(m_s[x],s_z[p_p[i].v]);//更新最大子树
}
}
m_s[x]=max(m_s[x],s_n-s_z[x]);
if(m_s[x]<m_s[g_g])g_g=x;//更新根节点
}
void a_d(int k_k,int x,int v){
int t=n_s[k_k].size();//当前的深度范围
while(x<t){//在范围内
n_s[k_k][x]+=v;//累计区间深度权值
x+=l_t(x);
}
}
void a_d2(int k_k,int x,int v){
int t=l_s[k_k].size();//上个根节点（重心）的范围
while(x<t){
l_s[k_k][x]+=v;//累计区间深度权值
x+=l_t(x);
}
}
int q_1(int k_k,int x){
int r_s=0;
if(x>=n_s[k_k].size())
x=(int)n_s[k_k].size()-1;
//限制区间范围（深度只有这些，范围再大也没用）
while(x){
r_s+=n_s[k_k][x];//统计目标深度范围内的权值
x-=l_t(x);
}
return r_s;
}
int q_2(int k_k,int x){
int r_s=0;
if(x>=l_s[k_k].size())
x=(int)l_s[k_k].size()-1;
//限制区间范围（深度只有这些，范围再大也没用）
while(x){
r_s+=l_s[k_k][x];//统计目标深度范围内的权值
x-=l_t(x);
}
return r_s;
}
void c_1(int x,int f_a,int k_k){
s_z[x]=1;//初始化子树大小
d_p[x]=d_p[f_a]+1;//更新深度
i_d[k_k][x]=d_p[x];//记录深度
for(int i=h_d[x];i;i=p_p[i].n_t)//遍历所有相连的点
if(!b_b[p_p[i].v]&&p_p[i].v!=f_a){//没有当过重心并且不是父节点
c_1(p_p[i].v,x,k_k);//先遍历子节点
s_z[x]+=s_z[p_p[i].v];//更新子树大小
}
m_d_p=max(d_p[x],m_d_p);//更新最大深度
}
void c_2(int x,int f_a,int k_k,int k){
a_d(k_k,d_p[x],v_v[x]);
//当 k_k 为根节点时，x 节点的深度和权值传参
if(k)a_d2(k_k,i_d[k][x],v_v[x]);
//不是初始点，当 k_k 为根节点时，x节点在上一个重心的深度和权值
for(int i=h_d[x];i;i=p_p[i].n_t)//遍历所有相连的点
if(!b_b[p_p[i].v]&&p_p[i].v!=f_a)//没当过重心并且不是父节点
c_2(p_p[i].v,x,k_k,k);//继续遍历
}
void f_t(int x,int f_a,int h){
int m_x;
b_b[x]=1;//标记，当前节点当过重心了
m_d_p=0;//初始化最大深度
c_1(x,0,x);//处理每个节点深度和子树大小
for(int i=0;i<=m_d_p;++i)n_s[x].push_back(0);//初始化
for(int i=0;i<=h;++i)l_s[x].push_back(0);//初始化
m_x=m_d_p;//记录最大深度
c_2(x,0,x,f_a);//维护所有节点在当前重心和上一个重心时的区间和
for(int i=h_d[x];i;i=p_p[i].n_t){//遍历所有相连的点
if(b_b[p_p[i].v])continue;
s_n=s_z[p_p[i].v];//更新节点数量
//初始化（找别的重心）
g_g=0;
m_s[0]=0x3f3f3f3f;
d_f(p_p[i].v,x);//初始化新重心
f[g_g]=x;//更新父节点
f_t(g_g,x,m_x);//继续处理
}
}
int main(){
n=r_r(),m=r_r();
for(int i=1;i<=n;++i)v_v[i]=r_r();//读入每个城市的价值
for(int i=1;i<n;++i){//连边
int u=r_r(),v=r_r();
a_d(u,v);
a_d(v,u);
}
//初始化
g_g=0;
m_s[0]=0x3f3f3f3f;
s_n=n;//记录节点总数量
d_f(1,0);//找重心
f_t(g_g,0,0);//处理所有节点成为重心的情况
while(m--){//处理询问
int op=r_r(),x=r_r()^l_a,v=r_r()^l_a;//解密
if(!op){//统计权值
int f_x=f[x];//记录父节点
int l_x=x;//记录当前节点
int f_d;//记录深度
a_s+=q_1(x,v+1);//记录当前节点范围内的权值
while(f_x){//没有到根就一直爬
f_d=i_d[f_x][x]-1;//记录深度
if(v-f_d<0){//不在影响范围内
l_x=f_x;//记录这次节点
f_x=f[f_x];//往上爬
continue;
}
a_s+=q_1(f_x,v-f_d+1);//统计贡献
a_s-=q_2(l_x,v-f_d+1);//去重
l_x=f_x;//记录节点
f_x=f[f_x];//往上爬
}
printf("%d\n",(l_a=a_s));
a_s=0;
}else{//单点修改
int k_k=x;//记录节点
a_d(x,1,-v_v[x]+v);//当前节点区间修改
while(f[x]){//没有到根就一直爬
int f_d=i_d[f[x]][k_k];//记录深度
//更新区间权值
a_d(f[x],f_d,-v_v[k_k]+v);
a_d2(x,f_d,-v_v[k_k]+v);
x=f[x];//往上爬
}
v_v[k_k]=v;//节点权值更新
}
}
return 0;
}
优化
这份代码不仅慢，空间也大，但可以过。。。
但是，可以优化。
时间空间优化
前置知识：树链剖分
在上面代码中，我们直接用一个二维数组（map 也占一维）将每个节点在不同重心时的深度记录下来了，但是由于本题的数据范围不是很大，所以 $O(\log n)$ 和一个大常数差不多，不会过多影响时间效率，但是大大节省了空间。
我们将整颗树剖分一遍，首先我们用树剖是解决快速求出每个节点在不同重心时的深度，就是当前节点在不同重心的距离，那么我们就可以通过树剖求两点的公共祖先，从而快速获得长度。
同时，上面为了防止浪费空间我们用的 map 存储。但是它的内部是红黑树，每多一个值都要插入，还要调整整棵树（unordered_map 效率更高，但是也很慢）。
所以，我们用树剖求 lca 实现了时空双赢！
优化代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cctype>
#include<map>
#include<vector>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e5+10;
int v_v[o_o<<1],h_d[o_o],n_t[o_o<<1],x_p;//链式前向星
void a_d(int u,int v){//加边
v_v[++x_p]=v;
n_t[x_p]=h_d[u];
h_d[u]=x_p;
}
bool b_b[o_o];//判断是否当过根节点
int s_z[o_o];//子树总量（子树节点个数）
int m_s[o_o];//最大子树
int s_n;//节点数量
int g_g;//根节点（当前重心）
void f_g(int x,int f_a){//处理重心
s_z[x]=1;//初始化子树重量
m_s[x]=0;//初始化最大子树
for(int i=h_d[x];i;i=n_t[i]){
int v=v_v[i];
if(!b_b[v]&&v!=f_a){//没有当过重心不是父节点
f_g(v,x);
s_z[x]+=s_z[v];//累计子树重量
m_s[x]=max(m_s[x],s_z[v]);//更新最大子树
}
}
m_s[x]=max(m_s[x],s_n-s_z[x]);
if(m_s[x]<m_s[g_g])g_g=x;//更新根节点（重心）
}
struct ss{
vector<int> v_l;
int l_n;
ss(){}
ss(int l_i){//初始化长度
l_n=l_i+1;
v_l.resize(l_i+2);
}
void g_a(int k,int v){//树状数组更新权值
for(int i=k+1;i<=l_n;i+=i&(-i))v_l[i]+=v;
}
int q_i(int k){//树状数组统计权值
int r_s=0;
for(int i=min(k+1,l_n);i>0;i-=i&(-i))r_s+=v_l[i];//注意边界
return r_s;
}
}n_x[o_o],l_x[o_o];
int i_d[o_o];//子树中节点编号
int n_i;//子树中节点的数量
int d_p[o_o];//节点深度
void s_l(int x,int f_a){//记录子树中所有节点
i_d[++n_i]=x;//进入队中
d_p[x]=d_p[f_a]+1;//更新深度
for(int i=h_d[x];i;i=n_t[i]){
int v=v_v[i];
if(!b_b[v]&&v!=f_a)s_l(v,x);//在子树中并且不是父节点继续找
}
}
int v_l[o_o];//节点权值
int l_i[o_o],r_i[o_o];//记录左右端点
int m_p[o_o];//当前节点的深度
int g_i[o_o];//记录节点的所属的根节点
void b_t(int k){//处理当前根节点整棵树的节点的深度，管辖范围深度对应的权值
n_i=0;//队列下标重置
d_p[k]=0;//初始化深度
int m_d_p=0;//初始化最大深度
for(int i=h_d[k];i;i=n_t[i]){
int v=v_v[i];
if(!b_b[v]){//在子树范围内
l_i[v]=n_i+1;//记录左端点
s_l(v,k);
r_i[v]=n_i;//记录右端点
m_p[v]=0;//初始化节点深度
for(int j=l_i[v];j<=n_i;j++)//范围内最大深度节点
m_p[v]=max(m_p[v],d_p[i_d[j]]);//当前节点子树中最大深度更新
m_d_p=max(m_d_p,m_p[v]);//更新总子树最大深度
}
}
//处理当前节点信息
n_x[k]=ss(m_d_p);//初始化长度
n_x[k].g_a(0,v_l[k]);//树状数组统计区间权值
for(int i=h_d[k];i;i=n_t[i]){
int v=v_v[i];
if(!b_b[v]){//子树范围内
int g_g=g_i[v];//记录根节点
l_x[g_g]=ss(m_p[v]);//更新子树长度
for(int j=l_i[v];j<=r_i[v];++j){//枚举子树元素
int x=i_d[j];//记录当前下表
//根据深度更新权值
n_x[k].g_a(d_p[x],v_l[x]);//更新当前节点权值
l_x[g_g].g_a(d_p[x],v_l[x]);//更新子树节点权值
}
}
}
}
int f_a[o_o];//记录父节点
void d_f(int x){
b_b[x]=1;//标记节点当过重心
for(int i=h_d[x];i;i=n_t[i]){
int v=v_v[i];
if(!b_b[v]){//在子树范围内（没当过重心）
s_n=s_z[v];//更新子树中节点数量
//更新重心
g_g=0;
f_g(v,0);
g_i[v]=g_g;//记录子树所属的根节点
f_a[g_g]=x;//记录父节点
}
}
b_t(x);//处理整棵树的相关信息
for(int i=h_d[x];i;i=n_t[i]){
int v=v_v[i];
if(!b_b[v])d_f(g_i[v]);//处理所有子节点
}
}
//树链剖分部分
int f_i[o_o];//父节点
int b_s[o_o];//字数最大子节点更新
int t_p[o_o];//记录链顶
void d_1(int x,int f_a){
s_z[x]=1;//初始化子树节点大小
f_i[x]=f_a;//更新父节点
d_p[x]=d_p[f_a]+1;//更新深度
for(int i=h_d[x];i;i=n_t[i]){
int v=v_v[i];
if(v!=f_a){//不是父节点（不会跑环）
d_1(v,x);
s_z[x]+=s_z[v];//累计子树大小
if(s_z[v]>s_z[b_s[x]])b_s[x]=v;//更新子树最大的子节点
}
}
}
void d_2(int x,int t_n){
t_p[x]=t_n;//记录链顶
if(!b_s[x])return;
d_2(b_s[x],t_n);//继续跑链
for(int i=h_d[x];i;i=n_t[i]){
int v=v_v[i];
if(v!=f_i[x]&&v!=b_s[x])d_2(v,v);//开新链
}
}
int l_a(int x,int y){//找公共祖先
while(t_p[x]!=t_p[y]){//跳到一条链上
if(d_p[t_p[x]]<d_p[t_p[y]])swap(x,y);
x=f_i[t_p[x]];//往回爬
}
return d_p[x]<d_p[y]?x:y;//节点小的时公共祖先
}
int g_d(int x,int y){//计算距离
return d_p[x]+d_p[y]-(d_p[l_a(x,y)]<<1);
}
int q_i(int x,int k){//查询
int r_s=n_x[x].q_i(k);//记录权值和
int k_k=x;
while(f_a[k_k]){
int d=g_d(f_a[k_k],x);//计算距离
if(d<=k)r_s+=n_x[f_a[k_k]].q_i(k-d)-l_x[k_k].q_i(k-d);
//统计路径上去重后的结果（注意在范围内的节点权值才统计）
k_k=f_a[k_k];//往回爬
}
return r_s;
}
void g_a(int x,int v){//单点修改
int k_k=v-v_l[x];//变化的值
if(!k_k)return;//没有变化不用改
v_l[x]=v;//改权值
n_x[x].g_a(0,k_k);//子树树状数组范围权值更新
int x_x=x;
while(f_a[x_x]){
int d=g_d(f_a[x_x],x);//计算距离
n_x[f_a[x_x]].g_a(d,k_k);//更新父节点范围权值和
l_x[x_x].g_a(d,k_k);//更新子树范围权值和
x_x=f_a[x_x];//往根处爬
}
}
int main(){
int n=r_r(),m=r_r();
for(int i=1;i<=n;++i)v_l[i]=r_r();//记录节点权值
for(int i=1;i<=n-1;++i){//加边
int u=r_r(),v=r_r();
a_d(u,v);
a_d(v,u);
}
m_s[0]=n+1;//初始化
s_n=n;//记录节点数量
f_g(1,0);//处理重心
d_f(g_g);//处理整个树的基本信息
//将整棵树剖分
d_1(1,0);
d_2(1,1);
int l_s=0;//记录上次结果，用于解密
while(m--){
int op=r_r(),x=r_r()^l_s,k=r_r()^l_s;//解密
if(op==0)printf("%lld\n",l_s=q_i(x,k));//询问范围内权值和
else g_a(x,k);//单点修改
}
return 0;
}
