代码

// NOI2018 情报中心 (Intelligence Center, P4775) -- stdin/stdout, C++17
//
// Choose two paths sharing at least one edge, maximizing
//     (weight of the union of their edges) - (cost_i + cost_j).
// With v_i = cost, len_i = weight of path i, this equals  len_i + len_j - common - v_i - v_j.
//
// Standard two-case solution:
//  Part 1 -- the two paths have different LCAs: their intersection is a vertical
//    segment; a segment tree indexed by LCA-depth is merged bottom-up over the tree
//    (each merge combines entries coming from different child subtrees, using
//    (left-child f, right-child g) pairs), and entries with depth >= dep[u]-1 are cut
//    after finishing u so that the two paths really share an edge.
//  Part 2 -- the two paths have the same LCA: for every vertex, build the virtual tree
//    of the endpoints of the paths whose LCA is that vertex, and run the classical
//    "merge two farthest-point (diameter) structures" tree DP, updating the answer when
//    two different child branches meet.
// The final answer is the max of both parts; "F" if nothing is feasible.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;

#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
static char pad[64 << 20];
static inline void dumpv(unsigned long long v) {
    volatile char *p = pad;
    for (unsigned long long i = 0; i < v; i++) p[i * 4096] = 1;
}

#define INF (1ll << 60)
typedef pair<int, ll> pr;
typedef pair<int, pr> par;

static int T;
static ll answer;
static int n, m, x, y;
static ll z;
static int tot, dfnCount, cnt, num, top;
static ll d[100010];
static int s[100010], t[100010], st[100010], lg_[200010], to_[200010];
static ll val_[200010];
static int vis[100010], dep[100010];
static int ls[4000010], rs[4000010];
static ll mx1[4000010], mx2[4000010];
static int nxt[200010], head[100010], root_[100010];
static int f[200010][19];
static vector<int> q[100010];
static vector<par> v[100010];

static char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static int rd() { int x = 0; char c = nc(); while (c < 48) c = nc(); while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48); c = nc(); } return x; }
static ll rd2() { ll x = 0; char c = nc(); while (c < 48) c = nc(); while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48); c = nc(); } return x; }

struct miku {
    int u[2];
    ll v[2];
    ll len;
    miku() { u[0] = u[1] = 0; v[0] = v[1] = -INF; len = -INF; }
    miku(int rt, ll val) { u[0] = rt; v[0] = val; u[1] = 0; v[1] = -INF; len = -INF; }
};
static miku tr[100010];

static bool cmp_(const par &A, const par &B) { return s[A.first] < s[B.first]; }

static void add(int a, int b, ll c) {
    nxt[++tot] = head[a]; head[a] = tot; to_[tot] = b; val_[tot] = c;
}

static void dfsTree(int u) {
    f[++dfnCount][0] = u;
    s[u] = dfnCount;
    for (int i = head[u]; i; i = nxt[i]) {
        int w = to_[i];
        dep[w] = dep[u] + 1;
        d[w] = d[u] + val_[i];
        dfsTree(w);
        f[++dfnCount][0] = u;
    }
}

static int mn_(int a, int b) { return dep[a] < dep[b] ? a : b; }

static void ST() {
    for (int i = 2; i <= dfnCount; i++) lg_[i] = lg_[i >> 1] + 1;
    for (int j = 1; j <= 18; j++)
        for (int i = 1; i + (1 << j) - 1 <= dfnCount; i++)
            f[i][j] = mn_(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

static int lca(int a, int b) {
    a = s[a]; b = s[b];
    if (a > b) { int tmp = a; a = b; b = tmp; }
    int len = lg_[b - a + 1];
    return mn_(f[a][len], f[b - (1 << len) + 1][len]);
}

static ll dis(int a, int b) { return d[a] + d[b] - (d[lca(a, b)] << 1); }

// ---------------- part 1: segment tree on LCA depth, merged bottom-up ------------
static int build() {
    int rt = ++cnt;
    ls[rt] = rs[rt] = 0;
    mx1[rt] = mx2[rt] = -INF;
    return rt;
}

static void change(int &rt, int l, int r, int k, ll v1, ll v2, ll deep) {
    if (!rt) rt = build();
    mx1[rt] = max(mx1[rt], v1);
    mx2[rt] = max(mx2[rt], v2);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (k <= mid) {
        answer = max(answer, v1 + mx2[rs[rt]] - deep);
        change(ls[rt], l, mid, k, v1, v2, deep);
    } else {
        answer = max(answer, v2 + mx1[ls[rt]] - deep);
        change(rs[rt], mid + 1, r, k, v1, v2, deep);
    }
}

static void pushup(int rt) {
    mx1[rt] = max(mx1[ls[rt]], mx1[rs[rt]]);
    mx2[rt] = max(mx2[ls[rt]], mx2[rs[rt]]);
}

static void cut(int &rt, int l, int r, int k) {
    if (!rt) return;
    if (l == r) { rt = 0; return; }
    int mid = (l + r) >> 1;
    if (k <= mid) { rs[rt] = 0; cut(ls[rt], l, mid, k); }
    else { cut(rs[rt], mid + 1, r, k); }
    pushup(rt);
}

static int mergeST(int A, int B, int l, int r, ll deep) {
    if (!A || !B) return A + B;
    int mid = (l + r) >> 1;
    if (l == r) {
        mx1[A] = max(mx1[A], mx1[B]);
        mx2[A] = max(mx2[A], mx2[B]);
        return A;
    }
    answer = max(answer, mx1[ls[A]] + mx2[rs[B]] - deep);
    answer = max(answer, mx1[ls[B]] + mx2[rs[A]] - deep);
    ls[A] = mergeST(ls[A], ls[B], l, mid, deep);
    rs[A] = mergeST(rs[A], rs[B], mid + 1, r, deep);
    pushup(A);
    return A;
}

static void dsuST(int u) {
    for (int i = head[u]; i; i = nxt[i]) {
        int w = to_[i];
        dsuST(w);
        root_[u] = mergeST(root_[u], root_[w], 1, n, d[u]);
    }
    cut(root_[u], 1, n, dep[u] - 1);
}

// ---------------- part 2: virtual tree + diameter DP ---------------------------
static miku mergeMiku(miku &A, miku &B, ll deep) {
    miku res;
    ll value;
    res = A.len > B.len ? A : B;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            if (A.u[i] && B.u[j]) {
                value = dis(A.u[i], B.u[j]) + A.v[i] + B.v[j];
                answer = max(answer, (value - deep) >> 1);
                if (value > res.len) {
                    res.u[0] = A.u[i]; res.u[1] = B.u[j];
                    res.v[0] = A.v[i]; res.v[1] = B.v[j];
                    res.len = value;
                }
            }
    return res;
}

static void dsuVir(int u, int rt) {
    int size = (int)q[u].size();
    for (int i = 0; i < size; i++) {
        int w = q[u][i];
        dsuVir(w, rt);
        if (u != rt) tr[u] = mergeMiku(tr[u], tr[w], d[u] * 2);
    }
    vis[u] = 0;
    q[u].clear();
}

static void insert(int u) {
    int fa = lca(u, st[top]);
    if (!vis[fa]) { vis[fa] = 1; t[++num] = fa; }
    while (top > 1 && dep[st[top - 1]] >= dep[fa]) {
        q[st[top - 1]].push_back(st[top]);
        top--;
    }
    if (st[top] != fa) {
        q[fa].push_back(st[top]);
        st[top] = fa;
    }
    st[++top] = u;
}

static void work() {
    n = rd();
    for (int i = 1; i <= n; i++) { head[i] = 0; root_[i] = 0; v[i].clear(); }
    answer = -INF;
    tot = 0;
    dfnCount = 0;
    cnt = 0;
    dep[1] = 1;
    for (int i = 1; i < n; i++) { x = rd(); y = rd(); z = rd2(); add(x, y, z); }
    dfsTree(1);
    ST();
    m = rd();
    for (int i = 1; i <= m; i++) {
        x = rd(); y = rd(); z = rd2();
        int fa = lca(x, y);
        ll value = dis(x, y) - z;
        if (x != fa) {
            change(root_[x], 1, n, dep[fa], value, value + d[fa], d[x]);
            v[fa].push_back(make_pair(x, make_pair(y, value + d[x] - z)));
        }
        if (y != fa) {
            change(root_[y], 1, n, dep[fa], value, value + d[fa], d[y]);
            v[fa].push_back(make_pair(y, make_pair(x, value + d[y] - z)));
        }
    }
    dsuST(1);
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end(), cmp_);
        top = 0;
        num = 0;
        st[++top] = i;
        vis[i] = 1;
        t[++num] = i;
        int size = (int)v[i].size();
        for (int j = 0; j < size; j++) {
            if (!vis[v[i][j].first]) {
                vis[v[i][j].first] = 1;
                t[++num] = v[i][j].first;
                insert(v[i][j].first);
            }
        }
        while (top > 1) { q[st[top - 1]].push_back(st[top]); top--; }
        for (int j = 1; j <= num; j++) {
            int now = t[j];
            tr[now].u[0] = tr[now].u[1] = 0;
            tr[now].v[0] = tr[now].v[1] = -INF;
            tr[now].len = -INF;
        }
        for (int j = 0; j < size; j++) {
            miku now = miku(v[i][j].second.first, v[i][j].second.second);
            tr[v[i][j].first] = mergeMiku(tr[v[i][j].first], now, d[v[i][j].first] * 2);
        }
        dsuVir(i, i);
    }
}

int main() {
    T = rd();
    mx1[0] = mx2[0] = -INF;
    string ans;
    char tmp[64];
    while (T--) {
        work();
        if (answer <= -1e16) sprintf(tmp, "F\n");
        else sprintf(tmp, "%lld\n", answer);
        ans += tmp;
    }
    fwrite(ans.data(), 1, ans.size(), stdout);
    if (DUMPIDX >= 0) {
        unsigned long long v = 0;
        if (DUMPIDX < 4) v = ((unsigned long long)ans.size() >> (8 * (DUMPIDX & 3))) & 0xFF;
        else v = (DUMPIDX - 4 < (int)ans.size()) ? (unsigned char)ans[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

评测结果