点分治
点分治，是一个很简单非常常见的数据结构
她是一种处理树上路径问题的工具，举个栗子：
给定一棵树和一个整数k，求树上边数等于k的路径有多少条
当树的节点数比较多的时候，就不能使用暴力了，我该怎么办
就要用点分治
原理
如图，我们在这棵树上选出一个root，那路径一共有三种情况：
1.在红子树中
2.在黑子树中
3.一半在红子树，一半在黑子树，要过root，拼成一条完整的路径
分类讨论，不存在的qaq，或许这辈子我也不会分类讨论
仔细想一下，实际情况1,2都珂以看做情况3，如图将答案中一点变成root，就成了情况3
好的上面只是思想，好像很虚空
我们需要实现
选根
选根的过程实际就是一个树形dp
选root是非常重要的，选不好会使复杂度爆炸
想想会发现这个根最好是树的重心
所以一个简单的树形dp就能搞定
inline void getroot(register int u,register int fa)
{
size[u]=1;
int num=0;
for(register int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa||vis[v])
continue;
getroot(v,u);
size[u]+=size[v];
num=Max(num,size[v]);
}
num=Max(num,sizee-size[u]);
if(mx>num)
mx=num,rt=u;
}
因为之后的分治过程还需要对子树单独找重心，所以代码中有vis，但是开始对整棵树无影响
分治
这才是点分治的精华qaq
根据代码来理解
inline ll devide(register int u)
{
ll res=solve(u,0); //把当前节点的答案加上去
vis[u]=true; //把节点标记，防止陷入死循环
int totsize=sizee;
for(register int i=head[u];i;i=e[i].next)
{
//分别处理每一棵子树
int v=e[i].to;
if(vis[v])
continue;
res-=solve(v,e[i].v); //容斥原理，下面说
rt=0,sizee=size[v]>size[u]?totsize-size[u]:size[v],mx=inf;
//把所有信息更新，递归进子树找重心，并继续分治
getroot(v,0);
res+=devide(rt);
}
return res;
}
大部分都应该比较好理解，除了ans-=slove(v,1）这句
我们先看一种情况：
在路径A->Root和B->Root合并时，这种情况显然是不合法的
所以要减去一些路径
完整代码
#include <bits/stdc++.h>
#define N 50005
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register ll x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[36];int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Max(register int a,register int b)
{
return a>b?a:b;
}
struct node{
int to,next,v;
}e[N<<1];
int head[N],tot=0;
inline void add(register int u,register int v,register int k)
{
e[++tot]=(node){v,head[u],k};
head[u]=tot;
}
int n,k;
int size[N];
int rt,sizee,mx;
bool vis[N];
ll ans=0;
ll d[N],q[N],l,r;
inline void getroot(register int u,register int fa)
{
size[u]=1;
int num=0;
for(register int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa||vis[v])
continue;
getroot(v,u);
size[u]+=size[v];
num=Max(num,size[v]);
}
num=Max(num,sizee-size[u]);
if(mx>num)
mx=num,rt=u;
}
inline void getdis(register int u,register int fa)
{
q[++r]=d[u];
for(register int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa||vis[v])
continue;
d[v]=d[u]+e[i].v;
getdis(v,u);
}
}
inline ll solve(register int u,register int val)
{
r=0;
d[u]=val;
getdis(u,0);
ll sum=0;
l=1;
sort(q+1,q+r+1);
while(l<r)
{
if(q[l]+q[r]<=k)
sum+=r-l,++l;
else
--r;
}
return sum;
}
inline ll devide(register int u)
{
ll res=solve(u,0);
vis[u]=true;
int totsize=sizee;
for(register int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(vis[v])
continue;
res-=solve(v,e[i].v);
rt=0,sizee=size[v]>size[u]?totsize-size[u]:size[v],mx=inf;
getroot(v,0);
res+=devide(rt);
}
return res;
}
int main()
{
n=read();
for(register int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
k=read();
sizee=n,mx=inf;
getroot(1,rt=0);
ans=devide(rt);
write(ans);
return 0;
}
动态点分治
一般，点分治只能处理静态的问题
但是，毒瘤的出题人加上了修改操作该怎么办qaq？
每修改一次做一次点分治？复杂度直接飞天
考虑一下，修改操作修改的是点权（不是树的结构，树的结构的话请找lct同学）
树的重心不会改变
先给出点分树的定义qaq：
点分治时每一层的重心连出的一个深度为logn的树
我们假设已经处理完了所有经过点1的路径，然后递归进子树继续点分，那么实际上原树被拆成了这么两棵树，两个重心分别为2和6
那么把第一层的重心和第二层的重心给连接起来（用红色表示）
然后我们继续进行点分，我们已经把经过点2和点6的所有路径都已经处理完了，那么子树又会继续拆分
然后因为子树大小只有1，重心就是他们自己，继续和上一层的重心连边
一棵点分树就这样建好了
在代码实现上实际只有一点点小的变动
inline void devide(register int u)
{
vis[u]=true;
int totsize=sizee;
for(register int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(vis[v])
continue;
rt=0,sizee=size[v]>size[u]?totsize-size[u]:size[v],mx=inf;
getroot(v,0);
fa[rt]=u;
devide(rt);
}
return res;
}
那么每一次修改，只要在点分树里不断往上跳，就能够维护整棵树的信息了
好像十分抽象，结合一道例题来讲或许会更好
题意简介：
给你了一棵树，每个节点有个权值（0/1），一开始所有点全是0
有一下两种操作：
C（Change）i，把i这个节点的权值取反
G（Game）查询距离最远的两个权值为0的点的距离
题解先咕咕咕