代码

// 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];
struct STNode { int ls, rs; int pad0, pad1; ll mx1, mx2; int pad2, pad3; };  // 32 B
static STNode *stn;
static int nxt[200010], head[100010], root_[100010];
static unsigned f[200010][19];   // packed: (dep << 16) | node
static int drank[100010], dleq[100010], dmark[100010], dD, gDD;
static int *cx_, *cy_, *cfa_;
static ll *cval_, *cwx_, *cwy_;
// virtual-tree adjacency as a flat linked list (no per-node vector)
static int qhead[100010], *qnxt, *qto, qcnt;
// chain-endpoint entries, bucketed by LCA vertex (CSR built with two counting sorts)
static int *eb_, *eg_, *ef_, *ek_, *estart_, *etmpb, *etmpg, *etmpf, *etmpk;
static ll *ew_, *etmpw;
static int *ecnt1, *epos1, *ecnt2, *epos2;
static int maxEntries;

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 inline unsigned pk(int u) { return ((unsigned)dep[u] << 16) | (unsigned)u; }

static void dfsTree(int u) {
    f[++dfnCount][0] = pk(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] = pk(u);
    }
}

static inline unsigned mn_(unsigned a, unsigned b) { return a < 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 (int)(mn_(f[a][len], f[b - (1 << len) + 1][len]) & 0xFFFFu);
}

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;
    STNode *q = stn + rt;
    q->ls = q->rs = 0;
    q->mx1 = q->mx2 = -INF;
    return rt;
}

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

static inline void pushup(int rt) {
    STNode *q = stn + rt;
    STNode *L = stn + q->ls, *R = stn + q->rs;
    q->mx1 = L->mx1 > R->mx1 ? L->mx1 : R->mx1;
    q->mx2 = L->mx2 > R->mx2 ? L->mx2 : R->mx2;
}

static void cut(int &rt, int l, int r, int k) {
    if (!rt) return;
    if (l == r) { rt = 0; return; }
    STNode *q = stn + rt;
    int mid = (l + r) >> 1;
    if (k <= mid) { q->rs = 0; cut(q->ls, l, mid, k); }
    else { cut(q->rs, 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;
    STNode *a = stn + A, *b = stn + B;
    if (l == r) {
        if (b->mx1 > a->mx1) a->mx1 = b->mx1;
        if (b->mx2 > a->mx2) a->mx2 = b->mx2;
        return A;
    }
    ll t1 = stn[a->ls].mx1 + stn[b->rs].mx2 - deep;
    if (t1 > answer) answer = t1;
    ll t2 = stn[b->ls].mx1 + stn[a->rs].mx2 - deep;
    if (t2 > answer) answer = t2;
    a->ls = mergeST(a->ls, b->ls, l, mid, deep);
    a->rs = mergeST(a->rs, b->rs, 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, gDD, d[u]);
    }
    int keep = (dep[u] >= 3) ? dleq[dep[u] - 2] : 0;   // ranks with depth <= dep[u]-2
    if (keep < dD) cut(root_[u], 1, gDD, keep + 1);   // k must stay inside [1, gDD]
}

// ---------------- part 2: virtual tree + diameter DP ---------------------------
static miku mergeMiku(miku &A, miku &B, ll deep) {
    miku res;
    res = A.len > B.len ? A : B;
    // dis(x,y) <= d[x] + d[y], so (d[x]+vx) + (d[y]+vy) upper-bounds the cross value:
    // skip pairs that can improve neither res.len nor the global answer.
    ll lim_res = res.len;                 // pair must beat this to change res
    ll lim_ans = answer * 2 + deep;       // pair must beat this to change answer
    ll limit = lim_res < lim_ans ? lim_res : lim_ans;
    for (int i = 0; i < 2; i++) {
        if (!A.u[i]) continue;
        ll av = A.v[i] + d[A.u[i]];
        for (int j = 0; j < 2; j++) {
            if (!B.u[j]) continue;
            if (av + B.v[j] + d[B.u[j]] <= limit) continue;
            ll value = dis(A.u[i], B.u[j]) + A.v[i] + B.v[j];
            ll cand = (value - deep) >> 1;
            if (cand > answer) answer = cand;
            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) {
    for (int e = qhead[u]; e; e = qnxt[e]) {
        int w = qto[e];
        dsuVir(w, rt);
        if (u != rt) tr[u] = mergeMiku(tr[u], tr[w], d[u] * 2);
    }
    vis[u] = 0;
    qhead[u] = 0;
}

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]) {
        int a2 = st[top - 1], b2 = st[top];
        qnxt[++qcnt] = qhead[a2]; qhead[a2] = qcnt; qto[qcnt] = b2;
        top--;
    }
    if (st[top] != fa) {
        qnxt[++qcnt] = qhead[fa]; qhead[fa] = qcnt; qto[qcnt] = 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; qhead[i] = 0; dmark[i] = 0; }
    answer = -INF;
    tot = 0;
    qcnt = 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();
    int ne = 0;
    for (int i = 0; i < m; i++) {
        x = rd(); y = rd(); z = rd2();
        int fa = lca(x, y);
        ll value = d[x] + d[y] - (d[fa] << 1) - z;      // dis(x,y) - z, reusing fa
        cx_[i] = x; cy_[i] = y; cfa_[i] = fa; cval_[i] = value;
        cwx_[i] = value + d[x] - z; cwy_[i] = value + d[y] - z;
        if (x != fa || y != fa) dmark[dep[fa]] = 1;
    }
    // ---- compress the LCA-depth domain to the depths that actually occur:
    //      the segment tree only needs the relative order of the depths.
    dD = 0;
    for (int dd = 1; dd <= n; dd++) {
        if (dmark[dd]) { dD++; drank[dd] = dD; }
        dleq[dd] = dD;
    }
    gDD = dD ? dD : 1;
    for (int i = 0; i < m; i++) {
        int fa = cfa_[i], xx = cx_[i], yy = cy_[i];
        int kk = drank[dep[fa]];
        if (xx != fa) {
            change(root_[xx], 1, gDD, kk, cval_[i], cval_[i] + d[fa], d[xx]);
            eb_[ne] = xx; eg_[ne] = yy; ew_[ne] = cwx_[i]; ef_[ne] = fa; ek_[ne] = s[xx]; ne++;
        }
        if (yy != fa) {
            change(root_[yy], 1, gDD, kk, cval_[i], cval_[i] + d[fa], d[yy]);
            eb_[ne] = yy; eg_[ne] = xx; ew_[ne] = cwy_[i]; ef_[ne] = fa; ek_[ne] = s[yy]; ne++;
        }
    }
    dsuST(1);
    // ---- order each bucket (LCA vertex) by dfn of its blue endpoint: two counting sorts
    for (int i = 0; i <= dfnCount; i++) ecnt1[i] = 0;
    for (int e = 0; e < ne; e++) ecnt1[ek_[e]]++;
    { int acc = 0; for (int i = 0; i <= dfnCount; i++) { epos1[i] = acc; acc += ecnt1[i]; } }
    for (int e = 0; e < ne; e++) {
        int p2 = epos1[ek_[e]]++;
        etmpb[p2] = eb_[e]; etmpg[p2] = eg_[e]; etmpw[p2] = ew_[e]; etmpf[p2] = ef_[e];
    }
    for (int i = 0; i <= n + 1; i++) ecnt2[i] = 0;
    for (int e = 0; e < ne; e++) ecnt2[etmpf[e]]++;                  // entries per LCA vertex
    { int acc = 0; for (int i = 0; i <= n + 1; i++) { estart_[i] = acc; epos2[i] = acc; acc += ecnt2[i]; } }
    for (int e = 0; e < ne; e++) {
        int p2 = epos2[etmpf[e]]++;
        eb_[p2] = etmpb[e]; eg_[p2] = etmpg[e]; ew_[p2] = etmpw[e]; ef_[p2] = etmpf[e];
    }
    for (int i = 1; i <= n; i++) {
        int bstart = estart_[i], bend = estart_[i] + ecnt2[i];
        if (bstart == bend) continue;                     // nothing to do for this vertex
        top = 0;
        num = 0;
        st[++top] = i;
        vis[i] = 1;
        t[++num] = i;
        for (int j = bstart; j < bend; j++) {
            int bp = eb_[j];
            if (!vis[bp]) {
                vis[bp] = 1;
                t[++num] = bp;
                insert(bp);
            }
        }
        while (top > 1) {
            int a2 = st[top - 1], b2 = st[top];
            qnxt[++qcnt] = qhead[a2]; qhead[a2] = qcnt; qto[qcnt] = b2;
            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 = bstart; j < bend; j++) {
            int bp = eb_[j];
            miku now = miku(eg_[j], ew_[j]);
            tr[bp] = mergeMiku(tr[bp], now, d[bp] * 2);
        }
        dsuVir(i, i);
    }
}

int main() {
    T = rd();
    stn = (STNode *)calloc(4000010, sizeof(STNode));
    stn[0].mx1 = stn[0].mx2 = -INF;
    maxEntries = 300005;
    eb_ = (int *)malloc(maxEntries * sizeof(int));
    eg_ = (int *)malloc(maxEntries * sizeof(int));
    ef_ = (int *)malloc(maxEntries * sizeof(int));
    ek_ = (int *)malloc(maxEntries * sizeof(int));
    ew_ = (ll *)malloc(maxEntries * sizeof(ll));
    etmpb = (int *)malloc(maxEntries * sizeof(int));
    etmpg = (int *)malloc(maxEntries * sizeof(int));
    etmpf = (int *)malloc(maxEntries * sizeof(int));
    etmpk = (int *)malloc(maxEntries * sizeof(int));
    etmpw = (ll *)malloc(maxEntries * sizeof(ll));
    estart_ = (int *)malloc(100010 * sizeof(int));
    ecnt1 = (int *)malloc(200010 * sizeof(int));   // key range = dfn range (2n)
    epos1 = (int *)malloc(200010 * sizeof(int));
    ecnt2 = (int *)malloc(100010 * sizeof(int));
    epos2 = (int *)malloc(100010 * sizeof(int));
    cx_ = (int *)malloc(300005 * sizeof(int));
    cy_ = (int *)malloc(300005 * sizeof(int));
    cfa_ = (int *)malloc(300005 * sizeof(int));
    cval_ = (ll *)malloc(300005 * sizeof(ll));
    cwx_ = (ll *)malloc(300005 * sizeof(ll));
    cwy_ = (ll *)malloc(300005 * sizeof(ll));
    qnxt = (int *)malloc(600010 * sizeof(int));
    qto = (int *)malloc(600010 * sizeof(int));
    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;
}

评测结果