Powered by:NEFU AB-IN

Link

3555. 二叉树

• 题意

  给定一个 n 个结点（编号 1∼n）构成的二叉树，其根结点为 1 号点。
  进行 m 次询问，每次询问两个结点之间的最短路径长度。
  树中所有边长均为 1。

• 思路

  总体思路就是，求出所有结点到根节点的距离，再求出两个点的lca，用距离之和减去lca的距离即可

  

• 代码

  有注释版

  /* * @Author: NEFU AB-IN * @Date: 2022-08-04 09:00:27 * @FilePath: \Acwing\3555\3555.cpp * @LastEditTime: 2022-08-04 09:29:12 */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  void solve()
  {
        
  
      int n, m;
      cin >> n >> m;
      vector<int> g[n + 1], depth(n + 1), st(n + 1);
      vector<vector<int>> fa(n + 1, vector<int>(11)); // 因为n只有1000，所以指数开到10就够用
      for (int i = 1; i <= n; ++i)
      {
        
          int ls, rs;
          cin >> ls >> rs;
          if (ls != -1)
              g[i].push_back(ls);
          if (rs != -1)
              g[i].push_back(rs);
      }
  
      function<void(int)> bfs = [&](int root) {
        
          queue<int> q;
          q.push(root);
  
          //初始化depth
          depth[0] = 0; // 哨兵，用来防止越界，代表0的深度为0
          depth[root] = 1;
          st[root] = 1;
  
          while (SZ(q))
          {
        
              auto t = q.front();
              q.pop();
              for (auto v : g[t])
              {
        
                  if (!st[v])
                  {
        
                      st[v] = 1;
                      depth[v] = depth[t] + 1;
                      fa[v][0] = t; // fa数组初始化，v向上跳2的0次方，就是父节点，也就是t
                      for (int k = 1; k <= 10; ++k) // v向上跳2的k次方，也就是先跳2的k-1次方，再跳2的k-1次方
                      {
        
                          fa[v][k] = fa[fa[v][k - 1]][k - 1];
                      }
                      q.push(v);
                  }
              }
          }
      };
  
      function<int(int, int)> lca = [&](int a, int b) {
        
          if (depth[a] < depth[b]) // 让a成为要跳的那个
              swap(a, b);
          for (int k = 10; k >= 0; --k) // 开始往上跳，跳到和b同一层
              if (depth[fa[a][k]] >= depth[b])
                  a = fa[a][k];
          if (a == b) // 如果这时候相等了，说明b就是lca
              return a;
          // 否则一起往上跳，跳到他们的lca的下一层
          for (int k = 10; k >= 0; --k)
          {
        
              if (fa[a][k] != fa[b][k])
              {
        
                  a = fa[a][k];
                  b = fa[b][k];
              }
          }
          // 返回父节点即可
          return fa[a][0];
      };
  
      bfs(1);
  
      for (int i = 1; i <= m; ++i)
      {
        
          int x, y;
          cin >> x >> y;
          cout << depth[x] + depth[y] - 2 * depth[lca(x, y)] << '\n';
      }
  
      return;
  }
  
  signed main()
  {
        
      IOS;
      int T;
      cin >> T;
      while (T--)
      {
        
          solve();
      }
      return 0;
  }
  

  无注释版

  /* * @Author: NEFU AB-IN * @Date: 2022-08-04 09:00:27 * @FilePath: \Acwing\3555\3555.cpp * @LastEditTime: 2022-08-04 09:29:12 */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  void solve()
  {
        
  
      int n, m;
      cin >> n >> m;
      vector<int> g[n + 1], depth(n + 1), st(n + 1);
      vector<vector<int>> fa(n + 1, vector<int>(11));
      for (int i = 1; i <= n; ++i)
      {
        
          int ls, rs;
          cin >> ls >> rs;
          if (ls != -1)
              g[i].push_back(ls);
          if (rs != -1)
              g[i].push_back(rs);
      }
  
      function<void(int)> bfs = [&](int root) {
        
          queue<int> q;
          q.push(root);
  
          //初始化depth
          depth[0] = 0; // 哨兵
          depth[root] = 1;
          st[root] = 1;
  
          while (SZ(q))
          {
        
              auto t = q.front();
              q.pop();
              for (auto v : g[t])
              {
        
                  if (!st[v])
                  {
        
                      st[v] = 1;
                      depth[v] = depth[t] + 1;
                      fa[v][0] = t;
                      for (int k = 1; k <= 10; ++k)
                      {
        
                          fa[v][k] = fa[fa[v][k - 1]][k - 1];
                      }
                      q.push(v);
                  }
              }
          }
      };
  
      function<int(int, int)> lca = [&](int a, int b) {
        
          if (depth[a] < depth[b])
              swap(a, b);
          for (int k = 10; k >= 0; --k)
              if (depth[fa[a][k]] >= depth[b])
                  a = fa[a][k];
          if (a == b)
              return a;
          for (int k = 10; k >= 0; --k)
          {
        
              if (fa[a][k] != fa[b][k])
              {
        
                  a = fa[a][k];
                  b = fa[b][k];
              }
          }
          return fa[a][0];
      };
  
      bfs(1);
  
      for (int i = 1; i <= m; ++i)
      {
        
          int x, y;
          cin >> x >> y;
          cout << depth[x] + depth[y] - 2 * depth[lca(x, y)] << '\n';
      }
  
      return;
  }
  
  signed main()
  {
        
      IOS;
      int T;
      cin >> T;
      while (T--)
      {
        
          solve();
      }
      return 0;
  }