题解 P6072 【[MdOI2020] Path】
Sai0511
2020-02-11 01:08:05
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 \})$。
代码：
```cpp
#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;
}
```