2 条题解

  • 0
    @ 2025-5-14 14:54:44
    10
    1 2 12188248
    2 3 2060207469
    1 4 960096258
    1 5 681126748
    3 6 719580677
    6 7 2084644229
    4 8 730246277
    1 9 668729523
    9 10 1055107866
    
    2084644229
    
    • 0
      @ 2023-3-14 14:20:31

      双倍经验:P4551 最长异或路径

      #include <bits/stdc++.h>
      using namespace std;
      int n;
      vector<pair<int, int>> e[112345];
      int xorSum[112345];
      void dfs(int u, int fa)
      {
          for (int i = 0; i < e[u].size(); i++)
          {
              int v = e[u][i].first;
              int w = e[u][i].second;
              if (v == fa)
                  continue;
              xorSum[v] = xorSum[u] ^ w;
              dfs(v, u);
          }
      }
      // 0/1 trie
      int tot, rt;
      int l[112345 * 30], r[112345 * 30]; // 0/1 子节点
      int cnt[112345 * 30];               //是否存在数
      void init()
      {
          memset(l, -1, sizeof(l));
          memset(r, -1, sizeof(r));
          memset(cnt, 0, sizeof(cnt));
          tot = 1;
          rt = 1;
      }
      void insert(int x)
      {
          int now = rt;
          for (int i = 30; i >= 0; i--)
          {
              if (x & (1 << i))
              {
                  if (r[now] == -1)
                      r[now] = ++tot;
                  now = r[now];
              }
              else
              {
                  if (l[now] == -1)
                      l[now] = ++tot;
                  now = l[now];
              }
          }
          cnt[now]++;
      }
      int query(int x)
      {
          int now = rt;
          int res = 0;
          // cout << x << " ========\n";
          for (int i = 30; i >= 0; i--)
          {
              if (x & (1 << i))
              {
                  if (l[now] != -1)
                  {
                      now = l[now];
                      res = res | (1 << i);
                      // cout << 1;
                  }
                  else
                  {
                      now = r[now];
                      // cout << 0;
                  }
              }
              else
              {
                  if (r[now] != -1)
                  {
                      now = r[now];
                      res = res | (1 << i);
                      // cout << 1;
                  }
                  else
                  {
                      now = l[now];
                      // cout << 0;
                  }
              }
          }
          // cout << "\n";
          return res;
      }
      int main()
      {
          ios::sync_with_stdio(false);
          cin.tie(0);
          cin >> n;
          for (int i = 1; i <= n - 1; i++)
          {
              int u, v, w;
              cin >> u >> v >> w;
              e[u].push_back(make_pair(v, w));
              e[v].push_back(make_pair(u, w));
          }
          xorSum[1] = 0;
          dfs(1, 0);
          /*
          for (int i = 1; i <= n; i++)
              cout << xorSum[i] << " ";
          cout << "\n";
          */
          init();
          insert(xorSum[1]);
          int ans = 0;
          for (int i = 2; i <= n; i++)
          {
              ans = max(ans, query(xorSum[i]));
              insert(xorSum[i]);
          }
          cout << ans << "\n";
          return 0;
      }
      
      • 1

      「一本通 2.3 练习 5」The XOR-longest Path

      信息

      ID
      698
      时间
      1000ms
      内存
      512MiB
      难度
      4
      标签
      递交数
      27
      已通过
      17
      上传者