题解：Many Pairs

算法标签

• 树链剖分 / 欧拉序
• LCA（最近公共祖先）
• DFS 序 + 离线查询
• 树状数组（Fenwick Tree）
• 树上差分思想
• 树形动态规划

问题分析

题目给定一棵 $N$ 个节点的树和 $K$ 个带权值的条约（边）。对于每个节点 $u$ 作为根时，选择最多两个与根相邻的子树，求这些子树中包含的条约权值和的最大值。

核心思路

1. 问题转化

当以 $u$ 为根时，选择的管辖范围是：

• 根节点 $u$ 本身
• 最多两个与 $u$ 相邻的子树

一个条约 $(A,B,C)$ 被计入当且仅当 $A$ 和 $B$ 都在管辖范围内。

2. 关键观察

• 条约可能完全在某个子树内
• 条约可能横跨两个子树
• 条约可能部分在子树外
• 需要高效计算各种情况下的权值和

算法步骤

步骤1：预处理

dfs(1, 0);  // 计算DFS序、深度、父节点数组

• 计算每个节点的 DFS 序 $L[u], R[u]$
• 预处理倍增数组用于快速求 LCA
• 建立树状数组用于区间查询

步骤2：分类处理条约

将每个条约 $(A,B,C)$ 分为几种情况：

情况1：自环条约

if (e[i].a == e[i].b) {
    exC[e[i].a] += e[i].c;
}

$A = B$ 时直接加到对应节点的额外收益中。

情况2：跨越父子的条约

if (!In(e[i].a, e[i].b))
    exB[e[i].a] += e[i].c;
if (!In(e[i].b, e[i].a))  
    exB[e[i].b] += e[i].c;

记录每个节点与子树外节点相连的条约权值和。

情况3：在子树内的条约

if (In(e[i].a, e[i].b))
    exA[Get(e[i].b, depth[e[i].b] - depth[e[i].a] - 1)] += e[i].c;

记录从父节点进入子节点的条约权值。

步骤3：计算子树内权值和

使用离线查询 + 树状数组：

for (int i = 1; i <= k; i++)
    mdf[dfn[e[i].a]].push_back(MP(dfn[e[i].b], e[i].c));

for (int i = 1; i <= n; i++) {
    qry[L[i] - 1].push_back({L[i], R[i], i, -1});
    qry[R[i]].push_back({L[i], R[i], i, 1});
}

计算 $f[u]$：以 $u$ 为根的子树内所有条约的权值和。

步骤4：计算子树外权值和

类似步骤3，计算 $G[u]$：与 $u$ 的子树外节点相关的条约权值和。

步骤5：计算横跨父子边的权值和

计算 $h[u]$：一端在 $u$ 的子树内，另一端在 $u$ 的父节点的其他子树中的条约权值和。

步骤6：合并答案

选择两个子树

for (auto v : g[u])
    if (v != fno) {
        if (f[v] + exA[v] > mx1)
            mx2 = mx1, mx1 = f[v] + exA[v];
        else
            mx2 = max(mx2, f[v] + exA[v]);
    }
ans[u] = mx1 + mx2;

处理横跨两个子树的条约

if (anc != e[i].a && anc != e[i].b) {
    int u = Get(e[i].a, depth[e[i].a] - depth[anc] - 1);
    int v = Get(e[i].b, depth[e[i].b] - depth[anc] - 1);
    pro[u][v] += e[i].c;
    ans[anc] = max(ans[anc], f[u] + f[v] + exA[u] + exA[v] + pro[u][v]);
}

选择一个子树和外部

ans[u] = max(ans[u], G[u] + exB[u]);
for (auto v : g[u])
    if (v != fno)
        ans[u] = max(ans[u], G[u] + exB[u] + f[v] + exA[v] + h[v]);

复杂度分析

• DFS 预处理：$O(N)$
• LCA 预处理：$O(N \log N)$
• 树状数组操作：$O((N+K) \log N)$
• 总复杂度：$O((N+K) \log N)$，满足 $N,K \leq 2\times 10^5$ 的要求

算法优势

1. 高效处理大规模数据：利用树状数组和离线查询优化
2. 全面覆盖所有情况：细致分类处理各种条约位置
3. 利用树结构特性：通过 DFS 序将树结构转化为序列问题

适用场景

这种基于 DFS 序和离线查询的树形问题处理方法适用于：

• 需要在树上进行多种区间查询的问题
• 涉及子树和路径统计的问题
• 需要高效处理树上点对关系的问题

该算法通过巧妙的分类和高效的数据结构，成功解决了这个复杂的树形结构最优选择问题。