点分治


点分治

在开始树上点分治前,复习下树的直径,树的重点,以及深度,分治小知识。

树的直径

两遍$dfs()$,第一次求出直径的一个端点,第二次求出以该端点为根的最长路,即为直径。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
struct node {
    int to,next;
    int w;
}e[maxn];
int ecnt, head[maxn];
int dis[maxn];
void addedge2(int u, int v ,int w) {
    e[ecnt] = node{u, head[v], w}; head[v] = ecnt++;
    e[ecnt] = node{v, head[u], w}; head[u] = ecnt++;
}
void init()
{
    memset(dis,-inf, sizeof(dis));
    memset(head, -1, sizeof(head));
    ecnt = 0;
}
void dfs(int u, int fa, int d) { //传入当前深入的距离便于回溯
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (v == fa) continue;
        dis[v] = w + d;
        dfs(v, u, dis[v]);
    }
}
int main() {
    int n, m;
    init();
    scanf("%d%d", &amp;n, &amp;m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &amp;u, &amp;v, &amp;w);
        addedge2(u, v, w);
    }
    int st = 1;
    dfs(st, -1, 0);
    int idx = -1, MAX = -inf;
    for (int i = 1; i <= n; i++) {
        if (dis[i] > MAX)
            idx = i, MAX = dis[i];
    }
    dis[idx] = 0, MAX = -1;
    dfs(idx, -1, 0);
    for (int i = 1; i <= n; i++)MAX = max(MAX, dis[i]);
    return !printf("%d\n", MAX);
}

/ * 
Sample input
7 6
1 2 3
2 3 4
2 4 2
4 5 5
4 6 1
5 7 3

Sample output
14
 * /

树的重心

在树中找到一个点,使其所有的子树中最大的子树含有的节点是最少的。

  • 两遍搜索,第一次随便定一个根,搜出每个孩子的子节点son[u],第二遍搜出使得max(son[u],n-1-son[u])最小的节点,即为重心。
  • 转换成一遍搜索:在每次递归算一下儿子的最大值,每层算一下最大值的最小值。
//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
struct node {
    int to, next;
    int w;
}e[maxn];
int ecnt, head[maxn];
int son[maxn];
void addedge2(int u, int v,int w) {
    e[ecnt] = node{u, head[v], w}; head[v] = ecnt++;
    e[ecnt] = node{v, head[u]}, w; head[u] = ecnt++;
}
int n,m;
void init() {
    memset(son, 0, sizeof(son));
    memset(head, -1, sizeof(head));
    ecnt = 0;
}
int siz, ans;
bool vis[maxn];
void dfs1(int u, int fa) {
    son[u] = 1;
    int res = -inf;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa || vis[v]) continue;
        dfs1(v, u);
        son[u] += son[v];
        res = max(res, son[v] - 1);
    }
    res = max(res, n - son[u]);
    if (res < siz) {
        ans = u;
        siz = res;
    }
}
int main() {
    init();
    scanf("%d%d", &amp;n, &amp;m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &amp;u, &amp;v, &amp;w);
        addedge2(u, v, w);
    }
    int st = 1;
    memset(vis, 0, sizeof(vis));
    ans = 0, siz = inf;
    dfs1(st, 0);
    printf("%d\n", ans);
}
/*Sample input
7 6
1 2 3
2 3 4
2 4 2
4 5 5
4 6 1
5 7 3

Sample output
4
*/
POJ 1655 模板题

题意:求出树的平衡因子balance即确定重心后最大子树规模-1,注意输出重心小的优先。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 20000 + 7;
const int inf = 0x3f3f3f3f;
int n;
int ans,ansIdx;
int son[maxn];
vector<int> g[maxn];
void dfs(int u, int fa) {
    int balance = 0;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) continue;
        dfs(v, u);
        son[u] += son[v] + 1;
        balance = max(balance, son[v] + 1);
    }
    balance = max(balance, n - son[u] - 1);
    if (balance < ans || balance == ans &amp;&amp; ansIdx > u)
        ans = balance, ansIdx = u;
}
int main() {
    int t; scanf("%d", &amp;t);
    while (t--) {
        scanf("%d", &amp;n);
        for (int i = 0; i <= n; i++) {
            son[i] = 0;
            g[i].clear();
        }
        ans = inf, ansIdx = 0;
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            scanf("%d %d", &amp;u, &amp;v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0);
        printf("%d %d\n", ansIdx, ans);
    }
    return 0;
}

树的点分治

一种高效的用来解决树上的路径问题的算法思想

以树的重心为根转换无根树为有根树,这样可以保证分而治之的子树规模相当,且有任何一颗子树的大小都不超过原来树大小的一半。

最坏情况下树会退化成一条链普通枚举要上到$O(n^2+n)$

#POJ 1741 Tree

题意:给出一棵树,问有多少$pair(u,v)$使得$dis(u,v)\le k$

暴力复杂度$O(n^2)$

分治思想:联想算法导论最大子数组的和,一条路径要么经过根节点,要么在根节点的一棵子树上,那么不妨对树“剖分”。

先求出经过根节点的路径数目,再对子树的根节点递归处理。
重点处理跨越根的路径。可套尺取,先求出到根节点的距离$dis[u]$,复杂度$O(n)$

排序$dis$问题转换成尺取,即在有序数组$dis$中找到数对满足和小于$k$,$O(n)$即可

但注意在降维后选择两点时会出现走重复路的情况也会被算在内,此时以孩子为实根,其父节点为虚根,dis[u]=e[i].w,减去在该虚根和实根下,路径长度小于k的对数。

#Code

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = int (1e5 + 7);
const int inf = 0x3f3f3f3f;
struct node{
    int to, next, w;
}e[maxn];
int head[maxn], ecnt;
int n,k;
void addedge(int u, int v, int w) {
    e[ecnt] = node{v, head[u], w};
    head[u] = ecnt++;
}
int vis[maxn];
struct Q_Q {
    int N;
    int subTMaxSize, CenterIdx;
    int sz[maxn];
    void dfs(int u, int fa) {
        sz[u] = 1;
        int res = 0; //此处不是平衡度,应是子树的大小,平衡度一个点为0
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (v == fa || vis[v]) continue; // 无向图两个都要判
            dfs(v, u);
            sz[u] += sz[v];
            res = max(res, sz[v] - 1);
        }
        res = max(res, N - sz[u]);
        if (res < subTMaxSize)
            subTMaxSize = res, CenterIdx = u;
    }
    int retCenter(int st) {
        subTMaxSize = inf, CenterIdx = 0;
        dfs(st, 0);
        return CenterIdx;
    }
};
Q_Q X_X;
int data[maxn], Len;
int dis[maxn];
int ANS;
void dfs(int u, int fa) {
    data[++Len] = dis[u];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        int w = e[i].w;
        if (v == fa || vis[v]) continue;
        dis[v] = dis[u] + w;
        dfs(v, u);
    }
}
int cal(int u, int now) {
    dis[u] = now; //更改u到虚根的距离
    Len = 0;
    dfs(u, 0);
    sort(data + 1, data + Len + 1);
    int res = 0;
    int l = 1, r = Len;
    while (l < r)
        if (data[r] + data[l] <= k)
            res += r - l++;
        else r--;
    return res;
}
void solve(int u) {
    ANS += cal(u, 0);
    //cal经过根u的路径数,在降维后要考虑选择的两个点都在根一侧
    vis[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        int w = e[i].w;
        if (vis[v]) continue;
        ANS -= cal(v, w); //除掉那些经过u的孩子h为根和v
        X_X.N = X_X.sz[v];
        // printf("Center root : %d\n",X_X.retCenter(v));
        solve(X_X.retCenter(v));
    }
}
void init(){
    ANS = 0;
    ecnt = 0;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
}
int main() {
    while (scanf("%d %d", &amp;n, &amp;k) != EOF, n + k) {
        init();
        for (int i = 1; i < n; i++) {
            int u, v, w;
            scanf("%d%d%d", &amp;u, &amp;v, &amp;w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        X_X.N = n;
        int st = 1;
        int root = X_X.retCenter(st);
#ifndef ONLINE_JUDGE
        printf("Root = %d\n", root);
#endif
        solve(root);
        printf("%d\n", ANS);
    }
    return 0;
}

KISS