点分治 算法学习

算法学习

前言

之前貌似也接触过，不过，早忘干净了

点分治基本

顾名思义，点分治就是对树上的点分治，从而进行一些操作。将点拆开，实则将树拆分成许多子树进行处理，并不断进行。

点分治选择

考虑讲一个点进行分治，首先选点(这不是废话吗)。那么如何选点呢？
对比：如果树是一条链，选择链端和链心时间复杂度是明显不同的，前者时间复杂度为 O(n), 而后者为 O(logn).
不难发现，选择的点的子树越大，效率越低，那我们怎么选呢？？
当然是树的重心啦
树的重心定义
树的重心也叫树的质心。对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点树最小。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。(from 百度百科)
伪代码

size[] 节点的子树大小
maxson[] 节点的最大子树的大小
Size 这棵树（当前处理的子树）的大小
Max 最大子树值
Root 重心，以重心为根
Getroot(u, fa){
    size[u] = 1, maxson[u] = 0;
    for(所有与 u 相连的点v) {
        if(未被访问 && v != fa) Getroot(v, u);
        size[u] += size[v];
        maxson[u] = max(maxson[u], size[v]);
    }
    maxson[u] = max(maxson[u], Size - size[u]);
    if(maxson[u] < Max) {Root = u, Max = maxson[u];}
}

点分治实现

看一道非常非常经典的例题吧
poj1741

题意

给一颗 $n$ 个节点的树，每条边上有一个距离 $v$ 。定义 $d(u,v)$ 为 $u$ 到 $v$ 的最小距离。给定 $k$ 值，求有多少点对 $（u，v）$ 使 $u$ 到 $v$ 的距离小于等于 $k$ 。
可以这样考虑，先假定一个根 Root, 接下来求出所有经过该点的路径中长度 <= k 的路径个数
那怎么求呢？？
对于一条树路径 只有经过或不经过一个点的情况，我们可以用总情况 - 所有不经过的情况就可以求出所有经过的情况啦

void Getans(int u) {
    Answer += Calc(u, 0);
    vis[u] = 1;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(!vis[v]) {
            Answer -= Calc(v, G[i].w);
            Size = size[v];
            Max = oo;
            Getroot(v, 0);
            Getans(Root);
        }
    }
    return ;
} 

line 2 求出的是以 $Root$ 为根时的所有情况
line 7 减去了所有不经过 Root 的路径条数
然后递归处理，重新选 $Root$ 处理 $u$ 的子节点

下面是一个计算函数
返回 $u$ 的子树中所有点到 $u$ 的距离 $+ len$ 之后
任意两点之间距离 $<= k$ 的点对个数
这里的 $+ len$ 处理是为了减去重复答案时方便处理
显然 上一个函数 line 2 时 $len$ 为 $0$

int Calc(int u, int len) {
    tot = 0;
    for(int i = 1; i <= n; i ++) dis[i] = 0;
    Getdis(u, 0, len);
    std:: sort(dis + 1, dis + tot + 1);
    int L = 1, R = tot, ret(0);
    while(L <= R) {
        if(dis[L] + dis[R] <= k) ret += (R - L), L ++;
        else R --;
    }
    return ret;
}

该题完整代码

#include <bits/stdc++.h>
const int N = 1e4 + 10;
const int oo = 1e9;
struct Node {int v, w, nxt;} G[N << 1];
int n, k, now = 1, head[N];
int size[N], maxson[N], dis[N];
bool vis[N];
int Max, Root, tot, Size;
int Answer;
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
inline void Add(int u, int v, int w) {G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;}
void Getroot(int u, int fa) {
    size[u] = 1;
    maxson[u] = 0;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(!vis[v] && v != fa) {
            Getroot(v, u);
            size[u] += size[v];
            maxson[u] = std:: max(maxson[u], size[v]);
        }
    }
    maxson[u] = std:: max(maxson[u], Size - size[u]);
    if(maxson[u] < Max) {Max = maxson[u]; Root = u;}
}
void Getdis(int u, int fa, int len) {
    dis[++ tot] = len;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(!vis[v] && v != fa) Getdis(v, u, len + G[i].w);
    }
}
int Calc(int u, int len) {
    tot = 0;
    for(int i = 1; i <= n; i ++) dis[i] = 0;
    Getdis(u, 0, len);
    std:: sort(dis + 1, dis + tot + 1);
    int L = 1, R = tot, ret(0);
    while(L <= R) {
        if(dis[L] + dis[R] <= k) ret += (R - L), L ++;
        else R --;
    }
    return ret;
}
void Getans(int u) {
    Answer += Calc(u, 0);
    vis[u] = 1;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(!vis[v]) {
            Answer -= Calc(v, G[i].w);
            Size = size[v];
            Max = oo;
            Getroot(v, 0);
            Getans(Root);
        }
    }
    return ;
} 
int main() {
    while(1) {
        n = read(), k = read();
        if((! n) && (! k)) break;
        now = 1;
        for(int i = 1; i <= n; ++ i) head[i] = -1, vis[i] = 0;
        for(int i = 1; i < n; ++ i) {
            int u = read(), v = read(), w = read();
            Add(u, v, w), Add(v, u, w);
        }
        Answer = 0;
        Max = oo;
        Size = n;
        Getroot(1, 0);
        Getans(Root);
        std:: cout << Answer << "\n";
    }
    return 0;
}