题解 P6072 【[MdOI2020] Path】

· · 题解

QwQ 原定验题人来发个题解。因为我太菜跑路了所以验题人就变成Kubic了。
一句话题意：选两条不相交的路径，使其边权的异或和的和最大。
首先分析一下两条路径不相交的性质。
设路径1的两个端点是a,b，它们的\text{lca}是p。路径2的两个端点是c,d，它们的\text{lca}是q。
情况1：当c在子树p内部而d在子树p外部时，c \rightarrow d一定与a \rightarrow b相交。
情况2：当c和d都在子树p外部时，c \rightarrow d一定不与a \rightarrow b相交。
当c,d都在子树p内部时，我们可以反过来讨论a \rightarrow b与q的关系。
情况3：当a在子树q内部而b在子树q外部时，同情况1。
情况4：当a和b都在子树q外部时，同情况2。
情况5：当a和b都在子树q内部时，p与q必交与一点，故这2条路径一定相交。
所以如果2条路径不相交则路径1一定在某一子树内，路径2一定在这个子树外。
接着40分做法就一目了然了：枚举一个点，然后枚举在这个子树内的点和这个子树外的点，使这两部分的异或和最大。可以用01\text{trie}做到\mathcal{O}(n^2\log \{ \max w_i\})。
结合一下链的部分分可以获得60分的好成绩。
接下来才是这题的核心，从60分到正解的过度。
考虑把问题放在序列上，设L(u)表示子树u的开始\text{dfs}序，R(u)表示子树u的结束\text{dfs}序。
则子树u对应的询问就是在[L(u),R(u)]选出2个异或和最大的数，在[1,L(u)-1] \cup [R(u)+1,n]中选出2个异或和最大的数。
发现这2个区间并不连续，比较麻烦。但是因为这2个区间的并相当于从整个序列中挖走了一段出来，所以把这个序列复制一遍加到末尾一定可以得到一个完整的连续的覆盖所有信息的区间。
到了这里其实这道题就结束了，我们相当于对于每个点创造出2个询问，这个点的答案就是这2个询问对应的区间的最大异或和之和。
可以用回滚莫队+\text{01trie}做到\mathcal{O}(n\sqrt{n}log \{ \max w_i \})。
代码：

#include <bits/stdc++.h>

const int N = 6e4 + 10;
int n, m, i, j, k, tot, totq, p = 1, trie_tot = 1, SZ, Ans;
int dfn[N], siz[N], bel[N], dis[N];
int fir[N], we[N << 1], to[N << 1], nxt[N << 1]; 
int ch[N * 26][2], tag[N * 26], ans[N];
struct ques {
  int l, r, id;
  ques() { l = r = id = 0; }
  ques(int _l, int _r, int i) {
    l = _l, r = _r, id = i; 
  }
  inline friend bool operator < (ques a, ques b) {
    if (bel[a.l] == bel[b.l]) return a.r < b.r;
    else return bel[a.l] < bel[b.l];
  }
} q[N << 1];  
inline void adde(int u, int v, int w) {
  static int ce = 0;
  to[++ce] = v, we[ce] = w, nxt[ce] = fir[u], fir[u] = ce;
}
inline void insert(int a) {
  int u = 1;
  for (int i = 30; i >= 0; i--) {
    bool v = (a >> i) & 1;
    if (!ch[u][v]) ch[u][v] = ++trie_tot;
    u = ch[u][v];
    tag[u]++;
  }
}
inline int query(int a) {
  int u = 1, res = 0;
  for (int i = 30; i >= 0; i--) {
    bool v = (a >> i) & 1;
    if (tag[ch[u][v ^ 1]]) res |= 1 << i, u = ch[u][v ^ 1];
    else u = ch[u][v]; 
  }
  return res;
}
inline void del(int a) {
  int u = 1;
  for (int i = 30; i >= 0; i--) {
    bool v = (a >> i) & 1;
    u = ch[u][v];
    tag[u]--;
  }
}
void dfs(int u, int par, int w) {
  siz[u] = 1, dfn[u] = ++tot, dis[dfn[u]] = dis[dfn[par]] ^ w;
  for (int i = fir[u], v; i; i = nxt[i]) 
    if ((v = to[i]) != par) {
      int w = we[i];
      dfs(v, u, w);
      siz[u] += siz[v];
    }
}
inline int calc(int l, int r) {
  int res = 0;
  for (int i = l; i <= r; i++) res = std::max(res, query(dis[i])), insert(dis[i]); 
  for (int i = l; i <= r; i++) del(dis[i]);
  return res;
}
inline void solve(int x) {
  int br = std::min(x * SZ, n), l = br + 1, r = br;
  int _ans = 0;
  for (; bel[q[p].l] == x; p++) {
    int ql = q[p].l, qr = q[p].r;  
    if (bel[qr] == x) { ans[q[p].id] += calc(ql, qr); continue; } 
    while (r < qr) _ans = std::max(_ans, query(dis[++r])), insert(dis[r]);
    int rev = _ans;
    while (l > ql) _ans = std::max(_ans, query(dis[--l])), insert(dis[l]);  
    ans[q[p].id] += _ans;
    while (l <= br) del(dis[l++]); _ans = rev;
  }
  while (r > br) del(dis[r--]);
}

int main() {
  scanf("%d", &n);
  for (int i = 1, u, v, w; i < n; i++) scanf("%d %d %d",&u, &v, &w), adde(u, v, w), adde(v, u, w); 
  dfs(1, 0, 0); 
  for (int i = 2; i <= n; i++) q[++totq] = ques(dfn[i], dfn[i] + siz[i] - 1, i), q[++totq] = ques(dfn[i] + siz[i], dfn[i] + n - 1, i);
  for (int i = 1; i <= n; i++) dis[i + n] = dis[i];
  n <<= 1; SZ = sqrt(n);
  for (int i = 1; i <= n; i++) bel[i] = (i - 1) / SZ + 1;
  std::sort(q + 1, q + totq + 1);
  for (int i = 1; i <= bel[n]; i++) solve(i);
  for (int i = 1; i <= n; i++) Ans = std::max(Ans, ans[i]);
  printf("%d\n", Ans);
  return 0;
}