题目分析

我们需要选择两条有公共边的路径，使得：

• 总收益 = 两条路径覆盖的所有边的价值之和 - 两条路径的代价之和
• 最大化这个值

关键点：

1. 树结构，n-1 条边
2. 路径是简单路径（树上唯一）
3. 两条路径必须有至少一条公共边

算法思路

核心观察

两条路径有公共边 ⇔ 它们的路径交非空

对于树上两条路径，判断是否有公共边可以通过：

• 求出两条路径的 LCA 和端点
• 检查路径交是否为空

暴力做法（小数据）

对于 $n \leq 100, m \leq 200$，我们可以：

1. 预处理 LCA
2. 对于每对方案 $(i, j)$：
   • 判断两条路径是否有公共边
   • 如果有，计算收益：覆盖边的价值和 - $v_i - v_j$
3. 取最大值

优化做法（大数据）

使用树链剖分 + 线段树：

1. 树链剖分：将树分解为链，便于路径操作
2. 路径标记：用线段树标记每条边被哪些路径覆盖
3. 快速计算：对于每条边，找到覆盖它的路径中收益最大的两条

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;

typedef long long ll;
const int MAXN = 100005;
const int MAXM = 200005;
const ll INF = 1e18;

struct Edge {
    int to, next, id;
    ll val;
} edge[MAXN * 2];

int head[MAXN], tot;
int n, m;

void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int id, ll val) {
    edge[tot] = {v, head[u], id, val};
    head[u] = tot++;
}

// 树链剖分相关
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN];
int top[MAXN], dfn[MAXN], rnk[MAXN], cnt;
ll edgeVal[MAXN];  // 边权值，edgeVal[i] 表示 dfs 序为 i 的边权值

void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    son[u] = 0;
    
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) {
            son[u] = v;
        }
    }
}

void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++cnt;
    rnk[cnt] = u;
    
    if (son[u]) {
        dfs2(son[u], tp);
    }
    
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

// 方案信息
struct Scheme {
    int x, y;
    ll v;
    vector<int> edges;  // 路径覆盖的边
} schemes[MAXM];

// 计算路径覆盖的边
void getPathEdges(int u, int v, vector<int>& edges) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        // 添加 top[u] 到 u 的路径上的边
        for (int i = dfn[top[u]]; i < dfn[u]; i++) {
            edges.push_back(i);
        }
        u = fa[top[u]];
    }
    if (u != v) {
        if (dep[u] < dep[v]) swap(u, v);
        for (int i = dfn[v]; i < dfn[u]; i++) {
            edges.push_back(i);
        }
    }
}

// 判断两条路径是否有公共边
bool hasCommonEdge(const vector<int>& edges1, const vector<int>& edges2) {
    // 简单实现：检查两个边集是否有交集
    vector<int> intersection;
    set_intersection(edges1.begin(), edges1.end(),
                    edges2.begin(), edges2.end(),
                    back_inserter(intersection));
    return !intersection.empty();
}

// 计算路径覆盖的总价值
ll calcPathValue(const vector<int>& edges) {
    ll sum = 0;
    for (int eid : edges) {
        sum += edgeVal[eid];
    }
    return sum;
}

// 暴力解法 - 适用于小数据
ll solveSmall() {
    // 预处理每个方案的边集和总价值
    vector<ll> pathValue(m);
    vector<vector<int>> pathEdges(m);
    
    for (int i = 0; i < m; i++) {
        getPathEdges(schemes[i].x, schemes[i].y, pathEdges[i]);
        sort(pathEdges[i].begin(), pathEdges[i].end());
        pathValue[i] = calcPathValue(pathEdges[i]);
    }
    
    ll ans = -INF;
    bool found = false;
    
    // 枚举所有方案对
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            if (hasCommonEdge(pathEdges[i], pathEdges[j])) {
                ll totalValue = calcPathValue(pathEdges[i]) + calcPathValue(pathEdges[j]);
                // 去重：计算两条路径的并集的价值
                vector<int> unionEdges;
                set_union(pathEdges[i].begin(), pathEdges[i].end(),
                         pathEdges[j].begin(), pathEdges[j].end(),
                         back_inserter(unionEdges));
                totalValue = calcPathValue(unionEdges);
                
                ll cost = schemes[i].v + schemes[j].v;
                ll profit = totalValue - cost;
                
                ans = max(ans, profit);
                found = true;
            }
        }
    }
    
    return found ? ans : -INF;
}

int main() {
    freopen("center.in", "r", stdin);
    freopen("center.out", "w", stdout);
    
    int T;
    scanf("%d", &T);
    
    while (T--) {
        scanf("%d", &n);
        init();
        
        // 读入边
        for (int i = 1; i < n; i++) {
            int a, b;
            ll c;
            scanf("%d%d%lld", &a, &b, &c);
            addEdge(a, b, i, c);
            addEdge(b, a, i, c);
        }
        
        // 树链剖分
        cnt = 0;
        dep[0] = 0;
        dfs1(1, 0);
        dfs2(1, 1);
        
        // 建立边权值映射
        for (int u = 1; u <= n; u++) {
            for (int i = head[u]; i != -1; i = edge[i].next) {
                int v = edge[i].to;
                if (v == fa[u]) {
                    edgeVal[dfn[u]] = edge[i].val;
                    break;
                }
            }
        }
        
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d%d%lld", &schemes[i].x, &schemes[i].y, &schemes[i].v);
        }
        
        ll result = solveSmall();
        
        if (result == -INF) {
            printf("F\n");
        } else {
            printf("%lld\n", result);
        }
    }
    
    return 0;
}

算法优化

对于更大的数据范围，可以使用以下优化：

1. 基于边的统计

// 对于每条边，记录覆盖它的路径中收益最大的两条
struct BestTwo {
    ll val[2];
    int id[2];
    
    BestTwo() {
        val[0] = val[1] = -INF;
        id[0] = id[1] = -1;
    }
    
    void update(ll newVal, int newId) {
        if (newVal > val[0]) {
            val[1] = val[0]; id[1] = id[0];
            val[0] = newVal; id[0] = newId;
        } else if (newVal > val[1]) {
            val[1] = newVal; id[1] = newId;
        }
    }
};

2. 使用树上差分标记路径

void markPath(int u, int v, int schemeId) {
    int l = lca(u, v);
    
    // 树上差分标记
    diff[u]++;
    diff[v]++;
    diff[l] -= 2;
    
    // 记录路径信息
    pathCover[u].push_back(schemeId);
    pathCover[v].push_back(schemeId);
    pathCover[l].push_back(-schemeId);  // 负号表示结束
}

复杂度分析

• 暴力解法：$O(m^2 \cdot n)$，适用于 $n \leq 100, m \leq 200$
• 优化解法：$O(m \log^2 n)$，使用树链剖分和线段树

关键点

1. 公共边判断：两条路径有公共边当且仅当它们的路径交非空
2. 收益计算：需要去重，同一条边只计算一次价值
3. 边界情况：可能所有方案对的收益都是负的，但只要有公共边就是合法的
4. 无解情况：没有任何两条路径有公共边时输出 F