倍增，DFS序，欧拉序和树的一些知识

本文主要是介绍倍增，DFS序，欧拉序和树的一些知识，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

倍增

定义

倍增法,顾名思义就是翻倍.

它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度

这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求LCA，无修改的路径信息。

路径最小值

注意:路径上的信息需要可以合并,例如求最值

const int N = 201000;
const int LOGN = 18;

int n, q;
int dep[N], par[N][LOGN + 1], val[N][LOGN + 1];
vector< pair<int,int> > e[N];

il void dfs(int u, int f)
{
  dep[u] = dep[f] + 1;
  for (auto p : e[u])
  {
    int v = p.fi;
    if (v == f) continue;
    par[v][0] = u;
    val[v][0] = p.second;
    dfs(v, u);
  }
}

int query(int u, int v)
{
  int ans = 1 << 30;
  if (dep[u] > dep[v]) swap(u, v);
  int d = dep[v] - dep[u];
  per(j,LOGN,0) if (d & (1 << j))
  {
    ans = min(ans, val[v][j]);
    v = par[v][j];
  }
  if (u == v) return ans;
  per(j,LOGN,0) if (par[u][j] != par[v][j])
  {
    ans = min(ans, min(val[u][j], val[v][j]));
    u = par[u][j];
    v = par[v][j];
  }
  ans = min({ans, val[u][0], val[v][0]});
  return ans;
}


int main(void) 
{
  clock_t c1 = clock();
  FastIO();
  cin >> n >> q;
  rep(i,1,n-1)
  {
    int u, v, w;
    cin >> u >> v >> w;
    e[u].pb(make_pair(v,w));
    e[v].pb(make_pair(u,w));
  } 
  dfs(1,0);
  //预处理掉这部分数据
  rep(j,1,LOGN) rep(u,1,n) 
  {
    par[u][j] = par[par[u][j-1]][j-1];
    val[u][j] = min(val[u][j-1], val[par[u][j-1]][j-1]);
  }
  rep(i,1,q)
  {
    int u, v;
    cin >> u >> v;
    cout << query(u, v) << '\n';
  }
  cerr << "Time Used:" << clock() - c1 << "ms" << endl;
  return 0;
}

DFS序

定义

树的DFS序列，也就是树的深搜序，它的概念是：树的每一个节点在深度优先遍历中进出栈的时间序列。

作用

可以把子树问题转化为序列问题,非线性问题变成线性问题求解,可以用上树状数组或者线段树等数据结构进行信息维护。

可以用来做带修改的子树信息这一类题目。

例题1

题面

给一颗n个点的树，有两个操作。

1. 1 x y， 把x的点权修改成y
2. 2 x，询问x点的子树点权和和到根的路径的点权和（含x点）

代码实现

两个树状数组，分别维护前缀和和差分。

前缀和数组用来维护子树点权和，差分数组用来维护到根的路径点全和。

const int N = 2e5 + 10;

template<class T>
struct BIT
{
  T c[N];
  int size;
  void resize(int s) 
  {
    size = s;
    rep(i,1,size) c[i] = 0;
  }
  void modify(int x, T d)
  {
    assert(x != 0);
    for (; x <= size; x += x & (-x)) c[x] += d;
  }
  T query(int x)
  {
    assert(x<=size);
    T s = 0;
    for (; x; x -= x & (-x)) s += c[x];
    return s;
  }
};

int n, q, tot;
int a[N],l[N],r[N];
vector<int> e[N];
BIT<ll> c1, c2;

il void dfs(int u, int f) 
{
  l[u] = ++tot;
  for (auto v : e[u]) if (v == f) continue; else dfs(v, u);
  r[u] = tot;
}

int main(void) 
{
  // clock_t c1 = clock();
  FastIO();

  cin >> n >> q;
  rep(i,2,n) 
  {
    int u, v;
    cin >> u >> v;
    e[u].pb(v), e[v].pb(u);
  }

  dfs(1, 0);
  c1.resize(n), c2.resize(n);
  rep(i,1,n) 
  {
    cin >> a[i];
    c1.modify(l[i], a[i]);
    c2.modify(l[i], a[i]);
    c2.modify(r[i] + 1, -a[i]);
  }
  
  rep(i,1,q)
  {
    int ty; cin >> ty;
    if (ty == 1)
    {
      int x, y;
      cin >> x >> y;
      int d = y - a[x];
      a[x] = y;
      c1.modify(l[x], d);
      c2.modify(l[x], d);
      c2.modify(r[x] + 1, -d);
    }
    else
    {
      int x;
      cin >> x;
      cout << c1.query(r[x]) - c1.query(l[x] - 1) << " ";
      cout << c2.query(l[x]) << '\n';
    }
  }
  // cerr << "Time Used:" << clock() - c1 << "ms" << endl;
  return 0;
}

DFS序列2

代码实现

const int N = 2e5 + 10;

template<class T>
struct BIT
{
  T c[N];
  int size;
  void resize(int s) 
  {
    size = s;
    rep(i,1,size) c[i] = 0;
  }
  void modify(int x, T d)
  {
    assert(x != 0);
    for (; x <= size; x += x & (-x)) c[x] += d;
  }
  T query(int x)
  {
    assert(x<=size);
    T s = 0;
    for (; x; x -= x & (-x)) s += c[x];
    return s;
  }
};

int n, q, tot;
int a[N],l[N],r[N];
vector<int> e[N];
vector< pair<int, int> > son[N];
BIT<ll> c1;

void dfs(int u, int f) 
{
  l[u] = ++tot;
  for (auto v : e[u]) 
  {
    if (v == f) continue; 
    else dfs(v, u);
    son[u].pb({l[v], r[v]});
  }
  r[u] = tot;
}

int main(void) 
{
  // clock_t c1 = clock();
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

  cin >> n >> q;
  rep(i,2,n) 
  {
    int u, v;
    cin >> u >> v;
    e[u].pb(v), e[v].pb(u);
  }
  int root = 1;
  dfs(1, 0);
  c1.resize(n);
  rep(i,1,n) 
  {
    cin >> a[i];
    c1.modify(l[i], a[i]);
  }
  
  rep(i,1,q)
  {
    int ty; cin >> ty;
    if (ty == 1)
    {
      int x, y;
      cin >> x >> y;
      int d = y - a[x];
      a[x] = y;
      c1.modify(l[x], d);
    }
    else if (ty == 3)
    {
      cin >> root;
    }
    else
    {
      int x;
      cin >> x;
      if (x == root) cout << c1.query(n) << '\n';
      else if (l[x] < l[root] && r[root] <= r[x])
      {
        auto seg = *prev(upper_bound(all(son[x]), pair<int,int>{l[root], r[root]}));
        cout << c1.query(n) - (c1.query(seg.second) - c1.query(seg.first - 1)) << '\n';
      }
      else cout << c1.query(r[x]) - c1.query(l[x] - 1) << '\n';
    }
  }
  return 0;
}

欧拉序

相比DFS序，多记录一层回溯的点。

const int N = 501000, LOGN = 20;

int n, q, p[N], tot, dep[N];
vector<int> e[N];
PII f[LOGN + 2][N * 2];
ll ans;

unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}

void dfs(int u, int par) 
{
  p[u] = ++tot;
  dep[u] = dep[par] + 1;
  f[0][tot] = {dep[u], u}; 
  for (auto v : e[u])
  {
    if (v == par) continue;
    dfs(v, u);
    f[0][++tot] = {dep[u], u};
  }
}

int main(){
  scanf("%d%d%u%u%u", &n, &q, &A, &B, &C);
  for (int i = 1; i < n; i++) 
  {
    int u, v;
    scanf("%d%d",&u,&v);
    e[u].pb(v);
    e[v].pb(u);
  }

  dfs(1, 0);
	for (int j = 1; j <= LOGN; j++) 
		for (int i = 1; i + (1 << j) - 1 <= tot; i++) 
			f[j][i] = min(f[j-1][i], f[j - 1][i + (1 << (j - 1))]);

  for (int i = 1; i <= q; i++) 
  {
    int l = p[rng61() % n + 1], r = p[rng61() % n + 1];
    if (l > r) swap(l, r);
		int len = 31 - __builtin_clz(r - l + 1);
    int d = min(f[len][l], f[len][r - (1 << len) + 1]).second;
    ans ^= 1ll * i * d;
  }
	printf("%lld\n",ans);
	return 0;
}

树

树的直径

树的直径是指树上任意两个节点之间最长.

树的直径的中间节点被称为树的中心,如果直径上有偶数个点,那么中间的两个节点都可以是树的中心.

树的中心到其他点的最长路径最短.

代码实现

int n, pre[N], c[N], q[N], dist[N];
int l, front = 1, rear = 0;
vector<int> e[N];

il void dfs(int x)
{
  for (auto y : e[x])
  {
    if (y != pre[x])
    {
      pre[y] = x;
      dist[y] = dist[x] + 1;
      dfs(y);
    }
  }
}

int main(void) 
{
  FastIO();
  
  cin >> n;
  rep(i,1,n-1)
  {
    int u, v;
    cin >> u >> v;
    e[u].pb(v), e[v].pb(u);
  }
  memset(dist, 0, sizeof(dist));
  memset(pre, 0, sizeof(pre));
  pre[1] = -1;
  dfs(1);
  int idx = 0, v = 0;
  rep(i,1,n)
  {
    if (dist[i] > v) v = dist[i], idx = i;
  }
  memset(dist, 0, sizeof(dist));
  memset(pre, 0, sizeof(pre));
  pre[idx] = -1;
  dfs(idx);
  v = 0;
  rep(i,1,n) v = max(v, dist[i]);
  cout << v << '\n';
  return 0;
}

树的重心

对于一颗无根树而言,当一个节点被选为根节点,它底下的每一个子节点的子树的大小最大值最小的那个点,被称为树的重心

删除重心后,树分裂成若干个子树,这若干个子树中的最大值最小.

性质

• 当重心为根节点时,它底下的每一个子树大小不大于整棵树大小的一半
• 重心到其他所有节点的距离和最小

代码实现

小数据\(O(logn)\)

const int N = 1e5 + 10;

int n, pre[1001], c[N], q[N], dist[N], f[N];
int l, front = 1, rear = 0;
vector<int> e[N];

il void dfs(int x)
{
  for (auto y : e[x])
  {
    if (y != pre[x])
    {
      pre[y] = x;
      dist[y] = dist[x] + 1;
      dfs(y);
    }
  }
}

il void solve(int x)
{
  ++cnt;
  for (auto y : e[x]) 
    if (y != pre[x]) 
      pre[y] = x, solve(y);
}

int main(void) 
{
  FastIO();
  
  cin >> n;
  rep(i,1,n-1)
  {
    int u, v;
    cin >> u >> v;
    e[u].pb(v), e[v].pb(u);
  }
  rep(i,1,n)
  {
    f[i] = 0;
    memset(pre, 0, sizeof(pre));
    for (auto y : e[i]) 
    {
      cnt = 0;
      pre[y] = i;
      solve(y);
      f[i] = max(f[i], cnt);
    }
  }
  // idx 重心
  int idx = 0, v = 1 << 30;
  rep(i,1,n) if (f[i] < v) v = f[i], idx = i;

  memset(dist, 0, sizeof(dist));
  memset(pre, 0, sizeof(pre));
  pre[idx] = -1;
  dfs(idx);
  int ans = 0;
  rep(i,1,n) ans += dist[i];
  cout << ans << '\n';
  return 0;
}

大数据

时间复杂度\(O(logn)\)

#include <bits/stdc++.h>
using namespace std;
#define DABIAO freopen("in.in","r",stdin);freopen("out.out","w",stdout);
#define debug(x...) do { cout << "\033[32;1m" << #x << " --> "; rd_debug(x); } while (0)
void rd_debug() {cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void rd_debug(const T& arg, const Ts&... args) { cout << arg << " "; rd_debug(args...); }
#define FastIO() ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define il inline
typedef long long ll;
typedef double db;
typedef pair<int, int> PII;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-6;
const int N = 1e5 + 10;

int n, pre[1001], c[N], q[N], dist[N], f[N];
int l, front = 1, rear = 0;
vector<int> e[N];

il void dfs(int x)
{
  for (auto y : e[x])
  {
    if (y != pre[x])
    {
      pre[y] = x;
      dist[y] = dist[x] + 1;
      dfs(y);
    }
  }
}

il void solve(int x)
{
  s[x] = 1;
  for (auto y : e[x]) 
    if (y != pre[x]) 
      pre[y] = x, solve(y), s[x] += s[y];
}

int main(void) 
{
  FastIO();
  
  cin >> n;
  rep(i,1,n-1)
  {
    int u, v;
    cin >> u >> v;
    e[u].pb(v), e[v].pb(u);
  }
  memset(pre, 0, sizeof(pre));
  pre[1] = -1;
  solve(1);

  int idx = 0, v = 1 << 30;
  rep(i,1,n)
  {
    int f = 0;
    for (auto y : e[i])
    {
      if (y != pre[i])
        f = max(f, s[y]);
      else 
        f = max(f, n - s[i]);
      if (f < v) v = f, idx = i;
    }
  }

  memset(dist, 0, sizeof(dist));
  memset(pre, 0, sizeof(pre));
  pre[idx] = -1;
  dfs(idx);
  int ans = 0;
  rep(i,1,n) ans += dist[i];
  cout << ans << '\n';
  return 0;
}		

LCA

求法

1. 先计算两个节点深度
2. 调整同一深度
3. 两个节点一起往上跳,直到两个节点相等

代码实现

小数据

时间复杂度\(O(n^2)\)

const int N = 1001;
int n, m, father[N], dist[N];
vector<int> e[N];

il void dfs(int x){  for (auto y : e[x]) dist[y] = dist[x] + 1, dfs(y);  }

int main(void) 
{
  clock_t c1 = clock();
  FastIO();
  cin >> n;
  rep(i,1,n) 
  {
    int x, y;
    cin >> x >> y;
    e[x].pb(y);
    father[y] = x;
  }
  memset(dist, 0, sizeof(dist));
  dfs(1);
  cin >> m;
  rep(i,1,m)
  {
    int x, y;
    cin >> x >> y;
    if (dist[x] < dist[y]) swap(x, y);
    int z = dist[x] - dist[y];
    rep(i,j,z) x = father[x];
    while (x != y) x = father[x], y = father[y];
    cout << x << '\n';
  }
  cerr << "Time Used:" << clock() - c1 << "ms" << endl;
  return 0;
}

大数据

时间复杂度\(O(logn)\)

int n, m, father[N], dist[N];
vector<int> e[N];

il void dfs(int x)
{
  for (auto y : e[x]) dist[y] = dist[x] + 1, dfs(y);
}

int main(void) 
{
  clock_t c1 = clock();
  FastIO();
  cin >> n;
  rep(i,1,n) 
  {
    int x, y;
    cin >> x >> y;
    e[x].pb(y);
    father[y][0] = x;
  }
  rep(i,1,20) rep(j,1,n)
    if (father[j][i - 1])
      father[j][i] = father[father[j][i-1]][i-1];
  memset(dist, 0, sizeof(dist));
  dfs(1);
  cin >> m;
  rep(i,1,m)
  {
    int x, y;
    cin >> x >> y;
    if (dist[x] < dist[y]) swap(x, y);
    int z = dist[x] - dist[y];
    for (int j = 0; j <= 20 && z; j++, z >>= 1)
      if (z & 1) x = father[x][j];
    if (x == y) {  cout << x << '\n'; continue;  }
    per(j,20,0) if (father[x][j] != father[y][j])
      x = father[x][j], y = father[y][j];
    cout << father[x][0] << '\n';
  }

  cerr << "Time Used:" << clock() - c1 << "ms" << endl;
  return 0;
}

用欧拉序来求LCA

const int N = 501000, LOGN = 20;

int n, q, p[N], tot, dep[N];
vector<int> e[N];
PII f[LOGN + 2][N * 2];
ll ans;

unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}

void dfs(int u, int par) 
{
  p[u] = ++tot;
  dep[u] = dep[par] + 1;
  f[0][tot] = {dep[u], u}; 
  for (auto v : e[u])
  {
    if (v == par) continue;
    dfs(v, u);
    f[0][++tot] = {dep[u], u};
  }
}

int main(){
  scanf("%d%d%u%u%u", &n, &q, &A, &B, &C);
  for (int i = 1; i < n; i++) 
  {
    int u, v;
    scanf("%d%d",&u,&v);
    e[u].pb(v);
    e[v].pb(u);
  }

  dfs(1, 0);
	for (int j = 1; j <= LOGN; j++) 
		for (int i = 1; i + (1 << j) - 1 <= tot; i++) 
			f[j][i] = min(f[j-1][i], f[j - 1][i + (1 << (j - 1))]);

  for (int i = 1; i <= q; i++) 
  {
    int l = p[rng61() % n + 1], r = p[rng61() % n + 1];
    if (l > r) swap(l, r);
		int len = 31 - __builtin_clz(r - l + 1);
    int d = min(f[len][l], f[len][r - (1 << len) + 1]).second;
    ans ^= 1ll * i * d;
  }
	printf("%lld\n",ans);
	return 0;
}

这篇关于倍增，DFS序，欧拉序和树的一些知识的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！