倍增LCA受到启发的一题

简介: 倍增LCA受到启发的一题

倍增过程中这里的 fa数组可以推广一下,保存每个点往根方向的路径上各个边/点的性质。常见的维护值有路径长度(树上求最短路)以及点的特殊性质(比如本题中各个农场的奶牛种类)等。

这里维护的数组d p [ i , j , o p ] ( o p = 1 或 者 o p = 0 ) dp[i,j,op] (op=1或者op=0)dp[i,j,op](op=1op=0)

维护的是i 点 往 树 根 方 向 走 2 j 步 经 过 没 经 过 o p i点往树根方向走2^j步经过没经过opi2jop

转移方程为:d p [ i , j , o p ] ∣ = ( d p [ i , j − 1 , o p ] ∣ d p [ f a [ i ] [ j − 1 ] , j − 1 , o p ] ) dp[i,j,op]|=(dp[i,j-1,op]|dp[fa[i][j-1],j-1,op])dp[i,j,op]=(dp[i,j1,op]dp[fa[i][j1],j1,op])

洛谷题目传送门

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
vector<int>g[N];
int n, m;
char s[N];
int fa[N][20];
int dep[N];
bool dp[N][20][2];//i走2^j步有没有经过1,0 转移方程 g[i,j,op]|=g[i,j-1,op]|g[fa[i,j-1],j-1,op];
int book[N];
int k;
void bfs(int root)
{
  memset(dep, 0x3f, sizeof(dep));
  dep[root] = 1;
  dep[0] = 0;
  queue<int>q;
  q.push(root);
  while (q.size())
  {
    int t = q.front();
    q.pop();
    for (auto x : g[t])
    {
      if (dep[x] > dep[t] + 1)
      {
        dep[x] = dep[t] + 1;
        q.push(x);
        fa[x][0] = t;
        dp[x][0][book[t]] = 1;
        for (int i = 1; i <= k; i++)
        {
          fa[x][i] = fa[fa[x][i - 1]][i - 1];
          dp[x][i][1] |= (dp[x][i - 1][1] | dp[fa[x][i - 1]][i - 1][1]);
          dp[x][i][0] |= (dp[x][i - 1][0] | dp[fa[x][i - 1]][i - 1][0]);
        }
      }
    }
  }
}
bool lca(int a, int b, bool f)
{
  if (dep[a] < dep[b]) swap(a, b);
  bool res = 0;
  for (int i = k; i >= 0; i--)
  {
    if (dep[fa[a][i]] >= dep[b])
    {
      res |= dp[a][i][f];
      a = fa[a][i];
    }
  }
  if (a == b)
  {
    return res;
  }
  for (int i = k; i >= 0; i--)
  {
    if (fa[a][i] != fa[b][i])
    {
      res |= dp[a][i][f];
      res |= dp[b][i][f];
      a = fa[a][i];
      b = fa[b][i];
    }
  }
  res |= dp[a][0][f];
  res |= dp[b][0][f];
  return res;
}
void solve()
{
  cin >> n >> m;
  cin >> s + 1;
  k = (int)(log(n) / log(2)) + 1;
  for (int i = 1; i <= n; i++)
  {
    if (s[i] == 'H') book[i] = 1;
    for (int j = 0; j <= k; j++)
      dp[i][j][book[i]] = 1;
  }
  for (int i = 1; i < n; i++)
  {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  bfs(1);
  for (int i = 1; i <= m; i++)
  {
    int x, y;
    char t;
    bool f = 0;
    cin >> x >> y >> t;
    if (t == 'H') f = 1;
    if (x == y)
    {
      cout << (book[x] == f);
    }
    else
    {
      bool res = lca(x, y, f);
      cout << res;
    }
  }
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int __ = 1;
  //cin>>__;
  while (__--)
  {
    solve();
  }
  return 0;
}


目录
相关文章
|
算法 Android开发 索引
LeetCode 周赛上分之旅 #44 同余前缀和问题与经典倍增 LCA 算法
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
81 0
|
5月前
|
机器学习/深度学习
技术经验解读:【最小生成树】新的开始(newstart)解题报告
技术经验解读:【最小生成树】新的开始(newstart)解题报告
27 0
|
5月前
|
存储
【洛谷 P2437】蜜蜂路线 题解(递归+记忆化搜索+高精度)
蜜蜂路线问题:蜜蜂从蜂房$m$到$n$($m&lt;n$)按数字递增爬行。给定$m$和$n$,求路线数。示例:$m=1$,$n=14$,输出$377$。100%数据$1\leq m,n\leq1000$。使用斐波那契序列优化,高精度处理大数。代码实现斐波那契存储并动态规划求解。
84 0
|
算法 Java 测试技术
LeetCode 周赛上分之旅 #46 经典二分答案与质因数分解
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
64 0
LeetCode 周赛上分之旅 #46 经典二分答案与质因数分解
|
机器学习/深度学习 算法
算法提高:组合数学| 卡特兰数的实现
卡特兰数列是组合数学中在各种计数问题中常出现的数列,其前几项为1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012…… 卡特兰数首先是由欧拉在计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,即在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数用Hn表示,Hn即卡特兰数。
145 0
算法提高:组合数学| 卡特兰数的实现
|
存储 移动开发 算法
C++/PTA 关于深度优先搜索和逆序对的题应该不会很难吧这件事
背景知识 深度优先搜索与 DFS 序 深度优先搜索算法(DFS)是一种用于遍历或搜索树或图的算法。以下伪代码描述了在树 T 上进行深度优先搜索的过程
116 0
|
算法 索引
从三道经典的leetcode题掌握二分法
前言 二分法是典型的搜索算法,其主要运用于有序序列中寻找目标值。其思路非常简单,就是不断比较搜索区间的中间值与目标值,当中间值等于目标值则结束搜索,如果中间值大于目标值,则继续搜索左半区间,反之搜索右半区间。 总结下,二分法就是在搜索过程中不断地将搜索区间减半,直到搜索到目标值或者搜索区间为空集。
|
算法 JavaScript 前端开发
日拱算法:解两道“杨辉三角”题
什么是“杨辉三角”,想必大家并不陌生~~ 在「杨辉三角」中,每个数是它左上方和右上方的数的和。
|
算法
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法
136 0
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法
|
机器学习/深度学习 算法
<<算法很美>>——(六)——回溯算法(下)—N皇后问题
<<算法很美>>——(六)——回溯算法(下)—N皇后问题
<<算法很美>>——(六)——回溯算法(下)—N皇后问题