一直以为树分治是个大块头，今天学习后发现基本的思想还是很好理解的。而做题不容易有思路，也是预料之中的，还需多加练习呐。
基于树链剖分的链分治没有很理解，点分治、边分治还是可以的。我决定暂且只学习点分治。
23:35-1:15
树的重心：
考察别人语文理解没意思。
POJ1655 定义了树的“平衡度”，删去某节点后使得生成的多棵树最“平衡”，该节点即为原树的重心。
树的大小为该树的节点个数。平衡：最大的子树 大小最小。
Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T.
For example, consider the tree:
Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two.
树上dfs 求重心与平衡度 O（n）
int ans[N],siz[N];//ans[i] 切掉i结点后的平衡值
int mn,mnid;
void dfs(int x,int ff)
{
siz[x]=1;
R(i,x){
int y=e[i].go;
if(y==ff) continue;
dfs(y,x);
siz[x]+=siz[y];
if(siz[y]>ans[x]) ans[x]=siz[y];
}
if(n-siz[x]>ans[x]) ans[x]=n-siz[x];
}
/*****main*****/
dfs(1,0);
mn=inf;mnid=0;
F(i,1,n){
if(ans[i]<mn) mn=ans[i],mnid=i;
}
printf("%d %d\n",mnid,mn);
树的重心的基本性质：
n个节点的树，删去重心后生成的多棵子树中，最大的树的大小<=n/2
==>以重心为根的树，从根开始dfs，每层递归的规模减半
==>树的深度O（logn），避免链造成的极端复杂度
树分治是一种算法。其中点分治更常见。
处理树上点对问题，即点对间的树上路径问题
点分治将其转化为经过根的满足一定条件的点对（路径）问题。
转化的方式是分治：
两点间的路径分为两种：
1、经过根
2、不经过根
对于第二种情况，从根的子节点层层递归找下去，一定存在一棵子树，使得这两点间的路径经过该子树的根。
那么只需递归处理第一种情况就好咯。
从树的根节点向下递归，每层处理出经过当前子树根节点的路径的信息。
每个节点都会被处理到，那么为了保证树的"平衡"，每层递归都将当前子树的重心作为当前子树的根。
即每次找到重心，然后把重心去掉，对分成的每两棵树之间分别统计路径信息（以重心的每个相邻点为根，遍历整棵子树即可得到这
个根到每个结点的统计信息），就可以知道包含这个重心的所有路径的信息。对于其他路径，即不经过根节点的路径，则向下递归，
进行同样的操作，直到单个叶节点为止。（Mato：注意这一个点所构成的路径有时也要处理一下）
每层进行什么操作呢？根据具体问题具体处理，反正整体和部分的操作是一致的。具体下文提到。
类比：边分治
每次找到一条边，使得删掉这条边后分成的两棵子树大小尽可能平均（保证复杂度），然后以删掉的边的两端点为根，分
别统计根到两棵树中的每个结点的路径信息，最后合并算路径，即可得到包含这条边的所有路径的信息，剩下的路径在两棵树中递归
处理。
进一步探讨&&点分治与边分治复杂度比较：（%Mato）：
对于不同的操作，每层有不同的处理方式：
1、操作可反（比如计数问题：统计某种路径的条数）：
补集转化的思想，由于子树之间互不相交，不需要进行容斥即可计数：
先将所有子树合在一起统计，再减去两端点处在相同子树内的路径信息。
2、操作不可反（比如找“最优路径”）：
不能采用上面的方法，只能枚举所有的子树对。
如果有S棵子树，则有O(S2)个子树对，最坏情况下（菊花树），S=N-1，
此时一一枚举子树对必然会导致总时间复杂度升到O(N2)以上。
解决办法：从小到大枚举子树，每处理完一棵子树就将其和前面的合并，此时算法效率取决于合并的方法。
如果使用归并法（大小为A的和大小为B的合并次数为A+B），对于星形树的合并总次数仍然为O(N2)，
如果能保证大小为A的和大小为B的合并次数为min{A, B}，则可以保证合并总次数在O(N)以内，从而可以保证总时间复杂度为O(NlogN)。
类比：边分治
由于分成的永远是两棵子树，所以在处理子树之间的关系上能够保证O(N)，
问题是它并不能保证每次分成的两棵子树大小非常平均，
在最坏情况下（菊花树），不管删哪条边分成的两棵子树大小都是一个1一个(N-1)，这样就会使总的时间复杂度上升为O(N2)。
——处理菊花树：加虚点，转化为二叉树，会导致常数较大
保证每个点的度数<=3，从而保证递归深度O（logn）
空间复杂度：O（n）
时间复杂度：O（nlog^2n）
具体问题：
给你一棵n 个点的树，树有边权，然后给定一个W，问有多少点对(u, v)，使得u,v 的距离大于等于W。(n<=10^5)
每层处理的问题：给定一棵有根树，根为p，问有多少点对(u,v)，使得lca(u,v) = p，且u,v 距离大于等于W。
双指针+计数问题补集转化
POJ1741 Tree(男人八题之一)
给你一棵n 个点的树，树有边权，然后给定一个W，问有多少点对(u, v)，使得u,v 的距离<=W。（n<=10^5）
解法同上，我参考了别人的代码，很棒的算法实现！
有很多细节要注意：
几个重要的函数：
GetRoot(int x,int ff) 找子树x的重心,作为“新根”（概念上的根，分治的分界）
GetDis(int x,int ff,int d)处理子树x中节点的dis:到当前子树"根"的距离
Cal(int x,int d) 处理子树x中所有满足dis[u]+dis[v]<=K的点对（路径）数
Work(int x) 分治处理主过程
1、ba[i]=balance(i)切掉i结点后的"平衡值":生成的子树中结点数最多的子树的结点数
ba[]的初值:
ba[rt]=inf或n;
GetRoot时：ba[x]=0,因为后面要取max,否则会T
if(ba[x]<ba[rt]) rt=x;//ba[rt]=ba[x]; 这句不加,使ba[rt]始终=inf或n,不需要重新赋值
2、补集转化的实现：
ans+=Cal(x,0);
R(i,x) if(!vis[e[i].go]) ans-=Cal(e[i].go,e[i].w);
故计数时，函数必须设置参数d!
3、Cal(int x,int d) 中，子树x中节点用cnt重新计数，因为不需要用到原有编号
双指针法计数，由于只要求<=K，这里只需维护一侧，统计以i为端点的路径条数
for(int i=1,j=cnt;i<j;i++){
while(dis[i]+dis[j]>K && i<j) j--;//注意while 及i<j限制
res+=(j-i);
}
i为其中一个端点，显然另一合法端点只能为i+1~j，所以个数不是(j-i+1)
4、递归函数设置了ff参数，但由于每次调用时，将当前子树根节点的ff赋值为0，
仍需加vis判断。
if(y==ff||vis[y]) continue;
My Code：
int n,rt,ans,total,cnt,ba[N],siz[N];
LL K,dis[N];
bool vis[N];
void GetRoot(int x,int ff)
{
siz[x]=1;ba[x]=0;//!!!
R(i,x){
int y=e[i].go;
if(y==ff||vis[y]) continue;
GetRoot(y,x);
siz[x]+=siz[y];
ba[x]=max(ba[x],siz[y]);
}
ba[x]=max(ba[x],total-siz[x]);
if(ba[x]<ba[rt]) rt=x;
}
void GetDis(int x,int ff,LL d)
{
dis[++cnt]=d;
R(i,x){
int y=e[i].go;
if(y==ff||vis[y]) continue;
GetDis(y,x,d+e[i].w);
}
}
int Cal(int x,LL d)
{
int res=0;
cnt=0;
GetDis(x,0,d);
sort(dis+1,dis+cnt+1);
for(int i=1,j=cnt;i<j;i++){
while(dis[i]+dis[j]>K && i<j) j--;
res+=(j-i);
}
return res;
}
void Work(int x)//递归处理x为根的子树(上一层递归已确定根!)
{
ans+=Cal(x,0);//处理的主体
vis[x]=true;
R(i,x){//向下一层递归转移
int y=e[i].go;
if(vis[y]) continue;//不需判断fa[]
ans-=Cal(y,e[i].w);//补集转化
rt=0;total=siz[y];
GetRoot(y,0);//找子树的重心(不是当前树的重心)
Work(rt);
}
}
/*****main*****/
siz[rt]=n;ba[rt]=n;//只是初值
total=n;GetRoot(1,0);
Work(rt);
POJ2114
十分蠢萌的题,包括题目描述（ahem>_<）
与上面的问题类似，模板题一个：
给你一棵n 个点的树，树有边权，然后给定一个W，问有多少点对(u, v)，使得u,v 的距离恰好等于W。（n<=10^5）
bzoj 2599 【IOI2011】Race
给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.(1 <= N <= 2*10^5，1 <= K <= 10^6)
评论 (0)
