前言
本来在学概率期望的，然而学长要讲点分治，好像还不讲板子于是过来学了。
点分治一般用于解决树上路径统计问题（满足某某条件的路径有多少条）。
顺便把点分树学了。
抄袭来源
「算法竞赛·进阶指南」？
#define
$siz(i)$：子树$i$的大小。
$ma(i)$：将点$i$从树中去掉后，产生的新子树中最大的$siz$。
树的重心：$ma$最小的点。
$dis(i)$：点$i$到根的距离。
$deep(i)$：点$i$到根的边数。
$tax$：桶。
$root$：当前分治中心。
树的重心
去掉一个点，产生的新子树就是它儿子和爹的子树，一个$O(n)$的做法就很显然了：
int siz[maxn],all,mx=inf,root;//all为原树大小,mx为当前ma最小的点，root为重心
void get_point(int node,int f){
siz[node]=1;
int x,ma=0;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x!=f)get_point(x,node),siz[node]+=siz[x],ma=max(ma,siz[x]);
}
ma=max(ma,all-siz[node]);
if(ma<mx)mx=ma,root=node;
}
点分治
实现
对于一棵树，路径无非有两种：经过根的路径和根子树内部的路径。
我们先统计出经过根的路径，再把根的每个子树递归下去。
当然会被链卡成$O(n^2)$的，选取树的重心递归就能稳定$O(n\log n)$。
栗子
在根的两个不同子树中取两个点$x,y$，满足$dis(x)+dis(y)=k$就满足条件。
$k$只有$1e7$，开个$1e7$的桶暴力统计即可。
代码
由于是自己yy的所以十分丑陋
int tax[10000001]={1},siz[maxn],h[maxn],all,ma,root,num,k;
bool vis[maxn],ans;
struct edge{
int pre,to,l;
}e[maxn<<1];
inline void add(int from,int to,int l){
e[++num].pre=h[from],h[from]=num,e[num].to=to,e[num].l=l;
}
void get_point(int node,int f=0){
siz[node]=1;
int mx=0,x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x!=f&&!vis[x])get_point(x,node),siz[node]+=siz[x],mx=max(siz[x],mx);
}
mx=max(mx,all-siz[node]);
if(mx<ma)ma=mx,root=node;
}
void Count(int node,int len,int v,int f=0){
if(len>k)return;
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x!=f&&!vis[x])Count(x,len+e[i].l,v,node);
}
tax[len]+=v;
}//计算答案
void calc(int node,int len,int f=0){
if(len>k)return;
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x!=f&&!vis[x])calc(x,len+e[i].l,node);
}
ans|=tax[k-len];
}//统计
void calc_siz(int node,int f=0){
siz[node]=1;
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x==f||vis[x])continue;
calc_siz(x,node),siz[node]+=siz[x];
}
}
void solve(int node){
int x;
vis[node]=1;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(!vis[x])calc(x,e[i].l),Count(x,e[i].l,1);//先算答案再统计，否则子树内部会影响
}
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(!vis[x])Count(x,e[i].l,-1);
}//清空桶子
calc_siz(node);
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(!vis[x])all=siz[x],ma=inf,get_point(x),solve(root);
}//递归计算子树
}
int main(){
int n=read(),m=read(),x,y,z;
for(register int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
while(m--)memset(vis,0,sizeof vis),k=read(),all=n,ma=inf,ans=0,get_point(1),solve(root),puts(ans?"AYE":"NAY");
}
点分树
单独拿出一个询问，不求树的直径，可以用点分治解决。
现在带修了，于是点分树来了。
实现
先考虑朴素的点分治。
为了方便点分树的食用，统计时用一种繁琐的方法：
对$root$的每个儿子，$dfs$算出子树内最大$deep$，选取最大的两个加和就是$root$的答案。
答案就是每个$root$的最大值。
注意到，修改一个点只会影响到它上面的$root$的答案，而每个点所属的$root$是$\log n$级别的！
把$root$向下一层的$root$连边，就能得到一棵最大深度为$\log n$的树，这就是点分树了。
一个点能影响的为其祖宗，修改直接暴力往上跳修改。
前面统计的都是最大值，为了能带修换成可删堆。
每个点记录在每个所属$root$的$deep$，在对应的堆插入/删除即可。
时间复杂度$O((m+n)\log^2 n)$，空间复杂度$O((m+n)\log n)$。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int d[maxn][21],t[maxn][21],siz[maxn],h[maxn],fa[maxn],dc[maxn],num,root,mx=inf,all,tp;
bool vis[maxn],is[maxn];
struct edge{
int pre,to;
}e[maxn<<1];
struct Heap{
priority_queue<int>q,d;
void push(int x){q.push(x);}
void del(int x){d.push(x);}
int top(){
while(!d.empty()&&q.top()==d.top())q.pop(),d.pop();
if(q.empty())return -inf;
return q.top();
}
int top2(){
int rec=top(),ans=0;
while(!d.empty()&&q.top()==d.top())q.pop(),d.pop();
if(!q.empty())q.pop(),ans=top();
q.push(rec);
return ans+rec;
}
}son[maxn<<1],rt[maxn],ans;
inline void add(int from,int to){
e[++num].pre=h[from],h[from]=num,e[num].to=to;
}
void getroot(int node,int f=0){
siz[node]=1;
int x,ma=0;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x==f||vis[x])continue;
getroot(x,node),siz[node]+=siz[x],ma=max(ma,siz[x]);
}
ma=max(ma,all-siz[node]);
if(ma<mx)mx=ma,root=node;
}
void init(int node,int f){
son[tp].push(d[node][++dc[node]]=d[f][dc[f]]+1),t[node][dc[node]]=tp;
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x==f||vis[x])continue;
init(x,node);
}
}
void calc_siz(int node,int f=0){
siz[node]=1;
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x==f||vis[x])continue;
calc_siz(x,node),siz[node]+=siz[x];
}
}
void build(int node){
rt[node].push(0),vis[node]=1;
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(vis[x])continue;
++tp,init(x,0),rt[node].push(son[tp].top());
}
ans.push(rt[node].top2());
calc_siz(node);
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(vis[x])continue;
all=siz[x],mx=inf,getroot(x),fa[root]=node,build(root);
}
}
int main(){
int n=read(),x,y,oop=n;
char s[3];
for(register int i=1;i<n;++i)x=read(),y=read(),add(x,y),add(y,x);
all=n,getroot(1),build(root);
int m=read();
while(m--){
scanf("%s",s);
if(s[0]=='C'){
x=read(),is[x]^=1;
if(is[x]){
--oop;
ans.del(rt[x].top2()),rt[x].del(0),ans.push(rt[x].top2());
for(register int i=dc[x],node=fa[x];node;--i,node=fa[node]){
ans.del(rt[node].top2());
rt[node].del(son[t[x][i]].top()),son[t[x][i]].del(d[x][i]),rt[node].push(son[t[x][i]].top());
ans.push(rt[node].top2());
}
}
else {
++oop;
ans.del(rt[x].top2()),rt[x].push(0),ans.push(rt[x].top2());
for(register int i=dc[x],node=fa[x];node;--i,node=fa[node]){
ans.del(rt[node].top2());
rt[node].del(son[t[x][i]].top()),son[t[x][i]].push(d[x][i]),rt[node].push(son[t[x][i]].top());
ans.push(rt[node].top2());
}
}
}
else {
if(!oop)puts("-1");
else if(oop==1)puts("0");
else printf("%d\n",ans.top());
}
}
}
水题
不知道受啥误导了看到单点加单点查就想用平衡树
聪聪可可
询问有多少条路径长度为$3$的倍数。
就是统计路径长度$\%3$等于$0$的路径条数，跟模板差不多。
Tree
询问有多少条路径长度$\le k$。
$calc$里查询$\le k-dis(i)$的点的数量，可以用树状数组维护，复杂度$O(n\log^2 n)$。
如果$k$更大的话可以用平衡树，清空也更方便。
Race
$k$只有$1e6$，开个桶记录$tax[len]$保存最小的$deep(i)$满足$dis(i)=len$，统计时答案对$deep(i)+tax[k-dis(i)]$取$\min$。
还可以有些小剪枝比如当$deep(i)\ge ans$时返回。
$zz$的我上来写了个$O(n\log^2 n)$的平衡树居然只比$O(n\log n)$正解慢$750ms$？
树的难题
重建计划
二分答案，把树上所有边权减去当前答案，检验是否存在长度大于$0$且边数满足条件的路径。
记录每个$deep$最大的$dis$。按$deep$排序，满足条件的$deep$是一个单向移动的区间，用单调队列维护最大值，为了消掉排序的$log$需要$bfs$实现。
由于同一子树内部的路径会互相影响，对每个子树都要清空单调队列重新统计。按子树内部最大$deep$排序后可以保证复杂度为$siz(root)$。
树上游戏
神仙题。有点分治、扫描线、树上差分、虚树等各种解法。
点分治我们考虑每种颜色的贡献。开一个数组$fir$。
$dfs$一遍子树，统计出子树大小，如果在某条链上点$i$的颜色第一次出现，就将它颜色的$fir$加上$siz(i)$。
统计答案，若颜色$i$从某个点到根路径上未出现过，就会产生$fir(i)$的贡献；否则会产生$siz(root)-siz(x)$的贡献（$x$为其所属子树）。
由于子树内部会互相影响，还需要先$dfs$一边减去当前子树的$fir$，统计完再加上。
剩下的就是全是细节的代码了。。。
快递员
点分树的题：
震波
建出点分树，每个点维护一棵平衡树，维护该点为$root$时每个深度的点权和。
对于修改，暴力往上跳，在平衡树内修改权值。
对于查询，暴力往上跳，查询平衡树内小于等于$k-dis$的权值和。
然后会发现多加了和$x$在同一子树的点的权值，还要维护每个$root$的每棵子树的信息减去。
平衡树有个十分优美的处理方法：
把每个深度的点权和提出来，直接依照这个数组build一棵平衡树。
我们发现修改操作直接找到对应深度的点修改即可。也就是说压根没有插入删除。
于是没必要写什么平衡树，直接裸上$BST$就行$QwQ$。
（darkbzoj过了bzoj被卡常了真是恶）
开店
还是每个点维护一棵$BST$，维护该点为$root$时每个颜色的距离和和出现次数。
暴力查每棵平衡树里颜色在$[L,R]$的距离和加上$dis$乘上出现次数。同样要减去同一子树的信息。
每个点度数不超过$3$可以用来优化常数不过我不会。
能在$loj$上$AC$，洛谷上$T$一个点。把$BST$换成$vector+$二分就卡过去了。
QTREE5
比较像栗子。
每个点用可删堆维护最小的$dis(i)$（$i$为白点）。
查询时跳父亲，答案对查询点到当前点距离+最小$dis$取$\min$。
为了去重要维护$root$的每个儿子的堆，若当前所属儿子的堆顶等于最小$dis$则取次小$dis$。
紫荆花之恋
替罪羊式重构点分树。
幻想乡战略游戏
随便定个根$r$，用$s_x$表示点$x$的子树和。
考虑把重心从$r$移到儿子$x$的代价：$dis(r,x)\times(s_r-s_x-s_x)$
若$x$比$r$优，则代价小于$0$，即$2s_x>s_r$。
再考虑把重心从$x$移到儿子$y$的代价：$dis(x,y)\times(s_r-s_y-s_y)$
若$y$比$x$优，则$2s_y>s_r$。
于是得到找重心的方法：从根节点不断走满足$2s>s_r$的节点，直到找不到为止。
这样太慢了，如果$2s_x>s_r$，则重心一定在$x$的子树里，从$x$的子树中找一个点走。每次找分治中心就能$\log$实现。
考虑拓展到点分树：把点分树建出来。假设$root$在上一层分治时属于$u$的子树。用点分树上$root$子树大小表示$u$的子树大小。但这样$u$所在的子树大小还少了原树中$u$上面的节点，可以把缺失的部分加到$u$的点权上，每往下走一步就给$u$加上$s_{fa[root]}-s_{root}$。
求出来重心后就是套路地用点分树查询答案了。
