首页 > 其他分享 >长链剖分

长链剖分

时间：2024-11-09 11:08:56浏览次数：1  
标签：长链 剖分 int len son read ans now

长链剖分

长链剖分在维护有关深度的信息时具有显著优势。

定义长链剖分中长儿子为子树内深度最大的儿子，不难使用类似重链剖分的方式求出长儿子：

void dfs1(int u, int f) {
    fa[u] = f, len[u] = 1;

    for (int v : G.e[u]) {
        if (v == f)
            continue;

        dfs1(v, u);

        if (len[v] >= len[u])
            son[u] = v, len[u] = len[v] + 1;
    }
}

性质

  • 一个节点到所在长链底部的路径为其到子树内所有节点的路径中最长的一条。
  • 任意节点 \(u\) 的 \(k\) 级祖先 \(f\) 所在链的长度一定 \(\geq k\) 。
  • 任意节点到达根节点经过的长链数是 \(O(\sqrt{n})\) 的，即最多经过 \(O(\sqrt{n})\) 条虚边。

应用

树上 k 级祖先

P5903 【模板】树上 k 级祖先

长链剖分可以做到 \(O(n \log n)\) 预处理， \(O(1)\) 查询。

预处理：

  • 每条长链的顶点和深度。
  • 倍增求出每个点的 \(2^k\) 级祖先。
  • 对于每条链，如果其长度为 \(len\) ，那么在顶点处记录顶点向上的 \(len\) 个祖先和向下的 \(len\) 个链上的点。

询问时利用倍增数组先将 \(x\) 跳到 \(x\) 的 \(2^{h_k}\) 级祖先（其中 \(h_k\) 表示 \(k\) 在二进制下的最高位）。设剩下还有 \(k^{\prime}\) 级，显然有 \(k^{\prime} < 2^{h_k}\) 。因此此时 \(x\) 所在的长链长度一定 \(\geq 2^{h_k} > k^{\prime}\) ，因此可以先将 \(x\) 跳到 \(x\) 所在链的顶点，若之后剩下的级数为正，则利用向上的数组求出答案，否则利用向下的数组求出答案。

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned int uint;
using namespace std;
const int N = 5e5 + 7, LOGN = 21;

struct Graph {
    vector<int> e[N];
    
    inline void insert(int u, int v) {
        e[u].emplace_back(v);
    }
} G;

int fa[N][LOGN];
int buf[N << 2], *up[N], *down[N], *now = buf;
int LOG[N], dep[N], len[N], son[N], top[N];

ll ans;
uint s;
int n, q, root;

template <class T = int>
inline T read() {
    char c = getchar();
    bool sign = (c == '-');
    
    while (c < '0' || c > '9')
        c = getchar(), sign |= (c == '-');
    
    T x = 0;
    
    while ('0' <= c && c <= '9')
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return sign ? (~x + 1) : x;
}

inline uint get(uint x) {
    return x ^= x << 13, x ^= x >> 17, x ^= x << 5, s = x;
}

inline void prework() {
    LOG[0] = -1;

    for (int i = 1; i <= n; ++i)
        LOG[i] = LOG[i >> 1] + 1;
}

void dfs1(int u) {
    dep[u] = dep[fa[u][0]] + 1, len[u] = 1;

    for (int i = 1; i < LOGN; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];

    for (int v : G.e[u]) {
        dfs1(v);

        if (len[v] >= len[u])
            son[u] = v, len[u] = len[v] + 1;
    }
}

void dfs2(int u, int topf) {
    top[u] = topf;

    if (u == topf) {
        up[u] = now, now += len[u];

        for (int i = 1, x = fa[u][0]; i <= len[u]; ++i, x = fa[x][0])
            up[u][i] = x;

        down[u] = now, now += len[u];

        for (int i = 1, x = son[u]; i <= len[u]; ++i, x = son[x])
            down[u][i] = x;
    }

    if (son[u])
        dfs2(son[u], topf);

    for (int v : G.e[u])
        if (v != son[u])
            dfs2(v, v);
}

inline int query(int x, int k) {
    if (!k)
        return x;

    x = fa[x][LOG[k]], k -= 1 << LOG[k];

    if (!k)
        return x;
    
    k -= dep[x] - dep[top[x]], x = top[x];
    return k ? (k > 0 ? up[x][k] : down[x][-k]) : x;
}

signed main() {
    n = read(), q = read(), s = read<uint>();
    prework();

    for (int i = 1; i <= n; ++i) {
        if (fa[i][0] = read())
            G.insert(fa[i][0], i);
        else
            root = i;
    }

    dfs1(root), dfs2(root, root);
    int lstans = 0;

    for (int i = 1; i <= q; ++i) {
        int x = (get(s) ^ lstans) % n + 1, k = (get(s) ^ lstans) % dep[x];
        ans ^= 1ll * i * (lstans = query(x, k));
    }

    printf("%lld", ans);
    return 0;
}

优化 DP

对于一类下标为深度的 DP，如果直接朴素实现，则可以通过构造一条链将时间复杂度卡到 \(O(n^2)\) 。

注意到一个点利用数组指针的变换，可以直接 \(O(1)\) 继承一个长儿子的信息，并添加当前点的信息。

考虑对每个点都继承长儿子的信息，暴力合并其他儿子的信息。

由于暴力合并的复杂度为短链的长度，所有链的长度之和是 \(O(n)\) 的，故暴力合并带来的总复杂度为 \(O(n)\) 。

CF1009F Dominant Indices

求子树内深度的众数。

\(n \leq 10^6\)

设 \(f_{i, j}\) 为 \(i\) 的子树内到 \(i\) 距离为 \(j\) 的节点数量，则：

\[\begin{aligned} f_{i, 0} &= 1 \\ f_{i, j} &= \sum_{v \in son_u} f_{v, j - 1} \end{aligned} \]

考虑优化，对于一个节点，先遍历它的重儿子，继承重儿子的结果，并添加当前点的信息。然后遍历轻儿子，将轻儿子的结果并到当前点上。

因为每条重链都只合并一次，时间复杂度 \(O(n)\) 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;

struct Graph {
    vector<int> e[N];
    
    inline void insert(int u, int v) {
        e[u].emplace_back(v);
    }
} G;

int buf[N], *f[N], *now = buf;
int fa[N], len[N], son[N], ans[N];

int n;

template <class T = int>
inline T read() {
    char c = getchar();
    bool sign = (c == '-');
    
    while (c < '0' || c > '9')
        c = getchar(), sign |= (c == '-');
    
    T x = 0;
    
    while ('0' <= c && c <= '9')
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return sign ? (~x + 1) : x;
}

void dfs1(int u, int f) {
    fa[u] = f, len[u] = 1;

    for (int v : G.e[u]) {
        if (v == f)
            continue;

        dfs1(v, u);

        if (len[v] >= len[u])
            son[u] = v, len[u] = len[v] + 1;
    }
}

void dfs2(int u) {
    auto cmp = [&](const int &a, const int &b) {
        return (f[u][a] == f[u][b] ? a < b : f[u][a] > f[u][b]) ? a : b;
    };

    f[u][0] = 1, ans[u] = 0;

    if (son[u])
        f[son[u]] = f[u] + 1, dfs2(son[u]), ans[u] = cmp(ans[u], ans[son[u]] + 1);

    for (int v : G.e[u]) {
        if (v == fa[u] || v == son[u])
            continue;

        f[v] = now, now += len[v], dfs2(v);

        for (int i = 0; i < len[v]; ++i)
            f[u][i + 1] += f[v][i], ans[u] = cmp(ans[u], i + 1);
    }
}

signed main() {
    n = read();

    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G.insert(u, v), G.insert(v, u);
    }

    dfs1(1, n);
    f[1] = now, now += len[1], dfs2(1);

    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);

    return 0;
}

P3899 [湖南集训] 更为厉害

给定一棵 \(n\) 个节点的有根树。定义：

  • 设 \(a \neq b\) ，若 \(a\) 是 \(b\) 的祖先，那么称“\(a\) 比 \(b\) 更为厉害”。
  • 设 \(a \neq b\) ，若 \(a\) 与 \(b\) 在树上的距离不超过某个给定常数 \(x\)，那么称“ \(a\) 与 \(b\) 彼此彼此”。

\(q\) 次询问，每次给出 \(p\) 和 \(k\)，求有多少个有序二元组 \((b, c)\) 满足：

  • \(p, b, c\) 互异。
  • \(p\) 和 \(b\) 都比 \(c\) 更为厉害。
  • \(p\) 和 \(b\) 彼此彼此，这里彼此彼此中的常数为给定的 \(k\) 。

\(n, q, \leq 3\times 10^5\)

首先，\(b\) 比 \(p\) 更为厉害的情况是好处理的，\(b\) 能任取 \(p\) 向上 \(k\) 个点，\(c\) 能在 \(p\) 子树中任取。下面讨论 \(p\) 比 \(b\) 更为厉害的情况。

设 \(f_{u, k} = \sum_{v \in T(u) - \{ u \}} [dist(u, v) \leq k] (siz_v - 1)\) 表示对于所有 \(v\) 满足 \(u\) 比 \(v\) 更为厉害且彼此彼此的答案，则：

\[f_{u, k} = \sum_{v \in son_u} f_{v, k - 1} + siz_v - 1 \]

长链剖分优化即可，实现时对于 \(siz_v - 1\) 的部分可以打全局标记实现。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3e5 + 7;

struct Graph {
    vector<int> e[N];
    
    inline void insert(int u, int v) {
        e[u].emplace_back(v);
    }
} G;

vector<pair<int, int> > qry[N];

ll buf[N], *f[N], *now = buf;
ll tag[N], ans[N];
int fa[N], dep[N], len[N], son[N], siz[N];

int n, m;

template <class T = int>
inline T read() {
    char c = getchar();
    bool sign = (c == '-');
    
    while (c < '0' || c > '9')
        c = getchar(), sign |= (c == '-');
    
    T x = 0;
    
    while ('0' <= c && c <= '9')
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return sign ? (~x + 1) : x;
}

void dfs1(int u, int f) {
    fa[u] = f, dep[u] = dep[f] + 1, len[u] = 1, siz[u] = 1;
    
    for (int v : G.e[u]) {
        if (v == f)
            continue;

        dfs1(v, u), siz[u] += siz[v];
        
        if (len[v] >= len[u])
            son[u] = v, len[u] = len[v] + 1;
    }
}

void dfs2(int u) {
    if (son[u])
        f[son[u]] = f[u] + 1, dfs2(son[u]), tag[u] = tag[son[u]] + siz[son[u]] - 1;
    
    for (int v : G.e[u]) {
        if (v == fa[u] || v == son[u])
            continue;

        f[v] = now, now += len[v], dfs2(v);
        tag[u] += tag[v] + siz[v] - 1;
        
        for (int j = 0; j < len[v]; ++j)
            f[u][j + 1] += f[v][j];
    }
    
    f[u][0] = -tag[u];
    
    for (auto it : qry[u])
        ans[it.second] += f[u][min(it.first, len[u] - 1)] + tag[u];
}

signed main() {
    n = read(), m = read();
    
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G.insert(u, v), G.insert(v, u);
    }
    
    dfs1(1, 0);
    
    for (int i = 1; i <= m; ++i) {
        int x = read(), k = read();
        ans[i] = 1ll * min(dep[x] - 1, k) * (siz[x] - 1);
        qry[x].emplace_back(k, i);
    }
    
    f[1] = now, now += len[1], dfs2(1);
    
    for (int i = 1; i <= m; ++i)
        printf("%lld\n", ans[i]);
    
    return 0;
}

P5904 [POI2014] HOT-Hotels 加强版

给出一棵有 \(n\) 个点的树，求有多少组点 \((i,j,k)\) 满足 \(i,j,k\) 两两之间的距离都相等。 \((i,j,k)\) 与 \((i,k,j)\) 算作同一组。

\(n \leq 10^5\)

设 \(f_{i, j}\) 表示满足 \(x\) 在 \(i\) 子树中且 \(dist(x, i) = j\) 的点的数量，\(g_{i, j}\) 表示满足 \(x, y\) 在 \(i\) 的子树内且 \(dist(lca(x, y), x) = dist(lca(x, y), y) = dist(lca(x, y), i) + j\) 的无序数对 \((x, y)\) 的数量。则：

\[ans \leftarrow g_{u, 0} \\ ans \leftarrow \sum_{v, w \in son(u), v \neq w} f_{v, i - 1} \times g_{w, i + 1} \\ g_{u, i - 1} \leftarrow \sum_{v \in son(u)} g_{v, i} \\ g_{u, i + 1} \leftarrow \sum_{v, w \in son(u), v \neq w} f_{v, i} \times f_{w, i} \\ f_{u, i + 1} \leftarrow \sum_{v \in son(u)} f_{v, i} \]

实现细节较多。

关于 \(g\) 开空间的解释：由于 g[son[u]] = g[u] - 1 ，所以 \(g_u\) 前面要开 \(len_u\) ；由于 \(g_{u, i}\) 中 \(i\) 的取值为 \([0, len_u)\) ，所以 \(g_i\) 后面也要开 \(len_u\) 。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;

struct Graph {
	vector<int> e[N];
	
	inline void insert(int u, int v) {
		e[u].emplace_back(v);
	}
} G;

ll buf[N * 3], *f[N], *g[N];
int fa[N], len[N], son[N];

ll *now = buf, ans;
int n;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

void dfs1(int u, int f) {
	fa[u] = f, len[u] = 1;
	
	for (int v : G.e[u]) {
		if (v == f)
			continue;
		
		dfs1(v, u);
		
		if (len[v] + 1 > len[u])
			len[u] = len[v] + 1, son[u] = v;
	}
}

void dfs2(int u) {
	if (son[u]) {
		f[son[u]] = f[u] + 1, g[son[u]] = g[u] - 1;
		dfs2(son[u]);
	}
	
	f[u][0] = 1;
	
	for (int v : G.e[u]) {
		if (v == fa[u] || v == son[u])
			continue;
		
		f[v] = now, now += len[v];
		now += len[v], g[v] = now, now += len[v];
		dfs2(v);
		
		for (int i = 0; i < len[v]; ++i)
			ans += g[u][i + 1] * f[v][i];
		
		for (int i = 1; i + 1 < len[v]; ++i)
			ans += f[u][i] * g[v][i + 1];

		for (int i = 1; i < len[v]; ++i)
			g[u][i - 1] += g[v][i];
		
		for (int i = 0; i < len[v]; ++i)
			g[u][i + 1] += f[u][i + 1] * f[v][i];

		for (int i = 0; i < len[v]; ++i)
			f[u][i + 1] += f[v][i];
	}

	ans += g[u][0];
}

signed main() {
	n = read();
	
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		G.insert(u, v), G.insert(v, u);
	}
	
	dfs1(1, 0);
	f[1] = now, now += len[1];
	now += len[1], g[1] = now, now += len[1];
	dfs2(1);
	printf("%lld", ans);
	return 0;
}

标签：长链,剖分,int,len,son,read,ans,now
From： https://www.cnblogs.com/wshcl/p/18536466/LongChainDivide

相关文章

  • HyperWorks的实体几何创建与六面体网格剖分
    创建和编辑实体几何在HyperMesh有限元前处理环境中，有许多操作是针对“实体几何”的，例如创建六面体网格。在创建实体网格的工作中，我们既可以使用闭合曲面创建实体网格，也可以使用完整的实体几何创建实体网格。与闭合曲面相比，使用实体几何作为操作对象更具优势：创建网格时仅需选择......
  • 树链剖分
    轻重链剖分性质重链重链内编号连续，可以用线段树维护一些值路径对于树上任意两点\(x,y\)，它们的路径经过的重链不超过\(logn\)条树剖正是运用这种方式，把1个修改/询问变成\(logn\)个修改/询问，然后高效求解注意：树剖的作用是将树上问题拆成\(logn\)个序列问题，并不是所有树剖都一......
  • CF1249F Maximum Weight Subset 题解 / 长链剖分复习
    CF1249FMaximumWeightSubset题解题目大意给定一个\(n\)个节点的树，每个节点有点权\(a_i\)。从中选出若干节点，要求这些点两两之间距离大于给定常数\(k\)，使得点权和最大。Solve给出一种线性做法。前置知识：长链剖分优化DP。考虑一个DP：设\(f(u,d)\)表示在\(u\)的子......
  • 树链剖分
    树链剖分重链剖分【问题引入】问题描述给定一颗有$n$个节点、带边权的树，现在有对树进行$m$个操作，操作有$2$类：将节点$a$到节点$b$路径上所有边权的值都改为$c$；询问节点$a$到节点$b$路径上的最大边权值。请你写一个程序依次完成这$m$个操作。有三个操作......
  • SpringBoot搭建webSocket长链接，实现双向实时通信
    很多网站为了实现推送技术，所用的技术都是轮询。轮询是在特定的时间间隔（如每1秒），由浏览器对服务器发出HTTP请求，然后由服务器返回最新的数据给客户端的浏览器。这种传统的模式带来很明显的缺点，即浏览器需要不断的向服务器发出请求，然而HTTP请求可能包含较长的头部，其中真正有效的数......
  • 长链剖分 入门
    长链剖分额，其实和树剖差不多，对于每个节点\(u\)维护\(mxd_u\)为子树内节点深度最大值。那么令\(Son(u)\)里取到\(mxd_v\)最大的儿子\(v\)为长儿子，类似重链剖分处理即可。同样令连接不同长链的两个点之间的边为虚边。有如下性质：从根到节点\(u\)，所经过虚边个数不超......
  • 【算法】树链剖分
    1.算法简介树链剖分为将树分割成若干条链，维护树上信息的思想。通常将其分为链后能用数据结构维护。树链剖分分为重链剖分，长链剖分，实链剖分。通常重链剖分最常用，本文主要介绍重链剖分。重链剖分可将树划分为一个个长度不超过\(O(\logn)\)的链，并且保证每条链内的\(dfs\)序......
  • 树链剖分笔记
    题单传送门2024.10.12P3038GrassPlantingG:DevC++栈空间开小了；调了三天啊三天线段树区间修改写成区间单点修改了；树剖往上跳写成了dep[u]<dep[v]而不是dep[top[u]]<dep[top[v]]2024.10.15P3128MaxFlowP:奇怪的TLE树剖DFS没把子树大小加到根上，重链剖分写成了后......
  • 树链剖分|树上启发式合并
    树链剖分分为重链剖分和长链剖分以及其他奇怪的剖分。以重剖为主。重链剖分将树上问题重链剖分为序列问题（经常是DFS序）然后用数据结构（经常是线段树）维护。剖分部分定义：重儿子：对于一个点，其儿子中，子树最大的那个；重边：父亲到重儿子的连边；轻儿子：除了重儿子以外的儿子；轻边：父亲......
  • 树链剖分
    考一遍，学一遍，忘一遍这里是重链剖分。两个dfs，第一个找重儿子，第二个找重链顶和dfn（注意要优先对重儿子dfs来保证同一条重链上的dfs序连续）查询和维护时一个一个跳重链顶端，时间复杂度O(nlogn)。常和线段树配套使用。模板#include<bits/stdc++.h>#definelllonglong#defineli......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99