深夜敲模板_3——树的点分治（poj1741解题报告）

具体算法可以看 2009 年的漆子超的论文

以合法点对为例：

进行分治，由于每次找的是重心，深度做多是log(n)。

大体来说就是

1：先找到该该数的重心，只需要把数遍历一遍就好了。复杂度：o(n)

2：计算各个节点到重心的距离。复杂度：o(n)

3：对重心距离进行排序，然后计算d[i]+d[j]<=k的合法点对。复杂度：排序o(nlog(n))，计算o(n)

所以总的复杂度为o(n*log(n)*log(n))

#include <iostream>
#include <cstring>
#define INF 1<<30
using namespace std;

struct Edge{
    int next,to;
    int w;
}edge[MAXN<<1]; ///边的信息

int son[MAXN];  ///该子树共有的节点数
int size;       ///分治以后一颗新树所包含的所有节点数
int list[MAXN]; ///保存遍历的这颗树的所有节点信息
int ss[MAXN];   ///保存所有节点的子树节点数的最大值
int d[MAXN];    ///保存节点到根的距离
bool vis[MAXN]; ///该节点有无删除

int k;          ///d[i]+d[j]<=k
int cnt;        ///边的个数
int num;        ///使节点值变成一个数列
int ans;        ///保存最终答案
int head[MAXN]; ///邻接表

void add_edge(int u,int v,int w){
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void init(){
    cnt = ans =0;
    memset(head,-1,sizeof(head));
    memset(vis,false,sizeof(vis));
}

///第一步，要找到重心作为根节点

void dfs_size(int u,int fa){
    list[size++] = u;
    son[u] = 1;
    int tem = -1;
    for(int i = head[u];i != -1;i = edge[i].next){
        int v = edge[i].to;
        if(!vis[i] && v != fa){
            dfs_size(v,u);
            son[u] += son[v];
            tem = max(tem,son[v]);
        }
    }
    ss[u] = tem;
}

int getroot(int u){
    size = 0;
    dfs_0(u,-1);
    int m_sum = INF,rt;
    for(int i = 0;i < size;i++){
        int v = list[i];
        ss[v] = max(ss[v],size-son[v]);
        if(ss[v] < m_sum){
            m_sum = ss[v];
            rt = v;
        }
    }
    return rt;
}

///计算所有节点到根的距离
void dfs_dist(int u,int dis,int fa){
    d[num++] = dis;
    for(int i = head[u];i != -1;i = edge[i].next){
        int v = edge[i].to;
        if(!vis[v] && v !=fa)   dfs_dist(v,dis+edge[i].w,u);
    }
}

///计算合法点对
int calc(int u,int dis){
    num = 0;
    dfs_dist(u,dis,-1);
    sort(d,d+num);
    int ret = 0;
    int i = 0,j = num-1;
    while(i < j){
        while(d[i]+d[j] > k && i < j)  j--;
        ret += (j-i);
        i++;
    }
    return ret;
}

///进行分治和计算最终答案
void dfs(int u){
    int rt = getroot(u);
    ans += calc(rt,0);
    vis[rt] = true;
    for(int i = head[rt];i != -1;i = edge[i].next){
        int v = edge[i].to;
        if(!vis[v]){
            ans -= calc(v,edge[i].w);
            dfs(v);
        }
    }
}