点分治学习语文学习

大致功能

计算静态树上的符合条件的路径的数量，长度等
eg

• 统计长度小于k的路径数量
• 经过特殊点不超过?个的最长路径长度

so为什么要用点分治呢？

路径经过两个点的lca，于是就被分成了两段！
统计答案的时候，实际上是找两段经过lca的路径配对，看合不合法。
分治，核心思想就是分成几个子问题求解，这几个子问题与总问题有一定的关联，综合起来就可以得出这个问题的解
这些路径端点都在子树中，子树中也有路径，总的情况与这些子树的情况是相关的，所以分别统计子树的情况，一通乱搞 就可以得出整个问题的解。
所以点分治便是起到了将总问题转化为子问题的作用

基本原理

对某棵正在处理的树，指定一个根root（重心）分别统计它的子树中的路径（点对），将这些子问题的答案综合起来，得到这棵树的答案
统计的方法大致分为两种

正难则反

首先，所有点到根的路径两两配对，归类为过根可重路径
显然这种路径分为两种：
1.起点和终点不在一棵子树中
2.在一棵中
直接算第一种的数量，势必要分C（nson,2）种情况，要用数据结构维护前面的情况，有些题目没必要
那么就借助容斥原理，用总的减掉不合法的，也就是第二种呗
第二种又等价于什么呢
设root的儿子为v，假设树已分层，儿子的层数较大
数量不就等于这棵子树中所有的过v可重路径吗！
这里注意统计的还是子树中的点到root的距离，所以要加起始距离，也就是到儿子的边权
（注意，是过v，不是过v的向下子树的实际的根（重心）！）
妙啊

直接统计

维护一个数据结构，记录已统计的子树的情况，统计新的子树时，便可找出与正在统计的路径（点）配对后符合条件的最优解或方案数，统计完这棵树后，再去更新数据结构
那么为什么要重心当根呢？如果直接把儿子当根的话，树每次分成的子树大小相差太大，有可能每次只分出非常小的几棵和非常大的一棵，所以分一棵的时候，复杂度可能会从log变成n，所以总的复杂度就呵呵了
所以要让这个根的子树的大小尽可能平均，所以可以选择重心作为某棵子树的根，相当于把这棵子树砍下来，把重心提起来，对他在进行分治！

O（n） 求重心的方法：

dfs遍历，（假设给树分层）计算每个点的向下子树的大小，若某个点的儿子的向下子树和父亲的向上子树的大小的最大值更小，则将根更新为它
那么，点分治间接统计的总的步骤就是这样：

1.求出根????

2.得到相关信息，统计第1类路径并累加入答案中

3.删除节点????，对于????的每一棵子树递归的执行分治算法

so 点分治最重要的思想是分治吗？

我这么问当然就不是的拉
我们的任务是统计
那么在什么里面寻找最方便呢？
当然是除了某个东西的属性之外，其他的特征比如顺序，结构什么都不用管的东西拉
要计数的话，直接做加减法最方便
要维护最值的话，只用考虑每个东西的值
那这个东西不就是

集合

吗？
（以下叙述引自三水）
“树有结构特征，有些点是等价的，而有些点不是。无根树的等价就是存在一种 点到点的映射使得两棵树完全一致
而树的结构非常多 所以在处理树上的问题的时候 往往都需要dfs 在获取树的结构信息之后才能去处理 比如如果暴力的去枚举每一个点对的话 每一次求解 其实都需要跑一次dfs才能得到这条路径
这是由树的结构决定
如果能把他转换成一个在集合上的问题 那么在操作的时候 所有基于树的结构信息都被忽略且不会对结果产生影响
“在同一颗子树中“是唯一对结果会产生影响的结构信息“
所以把过root的路径记为一个点对，放到一个集合中，这种思想就太巧妙了！利用容斥原理，把不符合的减掉，剩下的不就是答案吗！

应用

主要是思考如何设计统计的函数
一. 统计长度小于k的路径数
luoguP4178
间接法：尺取法+单调性：可以On求数组中满足某个约束的数对的数量
二.经过特殊点不超过?个的最长路径长度

#include <bits/stdc++.h>
using namespace std;
int n,k,e,root,ans,sizenow,size[200004],tmpdis[200004],maxsonsize[200004],head[200004],dis[200004];
bool isroot[200004];
struct node{
    int v,next,w;
}a[200001];
void insert(int u,int v,int d){
    a[++e].v=v;
    a[e].next=head[u];
    head[u]=e;
    a[e].w=d;
}

void findrt(int u,int fa){
    size[u]=1;
    maxsonsize[u]=0;
    //每次都初始化了，所以不会被之前的影响
    for(int p=head[u];p;p=a[p].next){
        int v=a[p].v;
        if(v==fa||isroot[v])continue;
        findrt(v,u);
        size[u]+=size[v];
        maxsonsize[u]=max(maxsonsize[u],size[v]);
    }
    maxsonsize[u]=max(maxsonsize[u],sizenow-size[u]);
    if(maxsonsize[u]<maxsonsize[root])root=u;

}
void getdis(int u,int fa){
    tmpdis[++tmpdis[0]]=dis[u]; 
    //表达式与上一个点没关系，就可以放循环外面，
    for(int p=head[u];p;p=a[p].next){
        int v=a[p].v;
        if(isroot[v]||v==fa)continue;
        dis[v]=dis[u]+a[p].w;
        getdis(v,u);
    }
}
int count(int u,int disnow){
    //计算u的向下子树中符合要求的路径数量
    tmpdis[0]=0;//不用一个个清零，记长度
    dis[u]=disnow;
    getdis(u,0);
    int num=0;
    sort(tmpdis+1,tmpdis+1+tmpdis[0]);
    int l=1,r=tmpdis[0];
    while(l<r){
        if(tmpdis[l]+tmpdis[r]<=k)num+=r-l,l++;
        //l+1到r都可以与l配对，加起来小于k
        else r--;
        //比l小的都不能和比r大的配对，那l+1就更不行了
    }
    return num;
}

void divide(int rt){
    isroot[rt] = 1;//mark root
    ans+=count(rt,0);//过root可重路径
    for(int p=head[rt];p;p=a[p].next){
        int v=a[p].v; 
        if(isroot[v])continue;
        ans-=count(v,a[p].w);//减掉s t都在一个子树中的路
        sizenow = size[v];  //要找G的子树的总大小
        root=0;
        findrt(v,0);//减的时候就顺便分一个
        divide(root);
    }
}
void clr(){
    root=0;
    ans=0, e=0;
    for(int i=1;i<=n;i++)isroot[i]=0,head[i]=0;;
}
int main(){
    cin>>n;
    int u,v,w;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d%d",&u,&v,&w);
        insert(u,v,w);
        insert(v,u,w);
    }
    cin>>k;
    maxsonsize[0]=sizenow=n;
    findrt(1,0);
    divide(root);
    cout<<ans<<endl;
}

免费旅行II(SPOJ 1825)

Description

在两周年纪念日的旅行之后，在第三年，旅行社SPOJ又一次踏上的打折旅行的道路。

这次旅行是ICPC岛屿上进行的，一个位于太平洋上，不可思议的小岛。我们列出了N个地点（编号从1到N）供旅客游览。这N个点由N-1条边连成一个树，每条边都有一个权值，这个权值可能为负。我们可以选择两个地点作为旅行的起点和终点。

由于当地正在庆祝节日，所以某些地方会特别的拥挤（我们称这些地方为拥挤点）。旅行的组织者希望这次旅行最多访问K个拥挤点。同时，我们希望我们经过的道路的权值和最大。

Input Format

第一行，三个整数N,K,M（1 <= N <= 200000, 0 <= K <=M, 0 <= M <= N）

之后的M行，每行一个拥挤点的编号。

最后的N-1行，每行三个整数u，v,l，代表u和v之间有一条权值为l的边

Output Format

一个整数，权值和最大的旅行线路

Sample Input

Copy
8 2 3
3
5
7
1 3 1
2 3 10
3 4 -2
4 5 -1
5 7 6
5 6 5
4 8 3
Sample Output#
Copy
12

直接法 树上直接统计：遍历儿子，使用一个数据结构，维护前面的儿子的向下子树情况，用于计算有关于这个儿子的向下子树的那部分可能的答案
对前i个儿子的向下子树维护一个树状数组，记录不超过k个特殊点时从root出发的路径长度的最大值，也就是前缀最大值，计算从root到这个儿子的向下子树中每个点的特殊点的数量m和距离，与前面的儿子经过特殊点不超过k-m个的最长路径相加更新总答案，再遍历一遍更新树状数组。等所有儿子遍历完之后遍历以遍儿子的子树，清除树状数组# 点分治学习语文学习

Views: 65