代码

// This code is AI-generated. (AI 生成的代码)
// NOI2018 情报中心.
// Pick two paths sharing an edge maximising (union edge value) - (cost of the
// two paths).  For a path x-y with z=LCA, split it at z into two chains.  Case 1:
// a segment-tree merge keyed by depth finds pairs whose intersection ends at the
// current node.  Case 2: group paths by z, build the virtual tree of their
// endpoints and merge diameters to find pairs whose intersection is an edge
// below the two z's.  O(1) LCA via Euler tour + sparse table.
#include <sys/auxv.h>
#include <cstdio>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

typedef long long ll;
using std::sort;

struct DuckInfo {
    uint64_t abi; const char *stdin_ptr; uint64_t stdin_size;
    char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
    char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
    const char *IB_ptr; uint64_t IB_limit;
    char *OB_ptr; uint64_t OB_limit; uint64_t tsc;
} __attribute__((packed));

enum { MAXN = 50005, MAXM = 100005, LG = 17 };
static const ll NEG = -(1LL << 60);
static const ll ANS_INIT = -(1LL << 59);

static int n, m;
static ll ans;

static int head[MAXN], ecnt;
struct Edge { int to, nxt; ll w; } edge[MAXN * 2 + 5];
static inline void addEdge(int u, int v, ll w) { edge[++ecnt] = {v, head[u], w}; head[u] = ecnt; }

static int par[MAXN], dep[MAXN];
static ll D[MAXN];
static int tin_[MAXN], tout_[MAXN], ord_[MAXN], ordcnt;
static int stk_[MAXN];

static int et_[MAXN * 2 + 5], det_[MAXN * 2 + 5], etcnt, first_[MAXN];
static int st_[LG][MAXN * 2 + 5];

static void buildTree() {
    par[1] = 0; dep[1] = 0; D[1] = 0;
    ordcnt = 0; int top = 1; stk_[1] = 1;
    while (top) {
        int x = stk_[top--];
        ord_[++ordcnt] = x; tin_[x] = ordcnt;
        for (int ei = head[x]; ei; ei = edge[ei].nxt) {
            int v = edge[ei].to;
            if (v == par[x]) continue;
            par[v] = x; dep[v] = dep[x] + 1; D[v] = D[x] + edge[ei].w;
            stk_[++top] = v;
        }
    }
    int maxd = 0;
    for (int i = 1; i <= n; ++i) { if (dep[i] > maxd) maxd = dep[i]; tout_[ord_[i]] = tin_[ord_[i]]; }
    for (int i = n; i >= 2; --i) { int x = ord_[i], p = par[x]; if (tout_[x] > tout_[p]) tout_[p] = tout_[x]; }
}

static void buildEuler() {
    etcnt = 0;
    static int sn[MAXN], se[MAXN];
    int top = 1;
    sn[1] = 1; se[1] = head[1];
    first_[1] = etcnt; et_[etcnt] = 1; det_[etcnt] = 0; etcnt++;
    while (top) {
        int x = sn[top], ei = se[top];
        while (ei && edge[ei].to == par[x]) ei = edge[ei].nxt;
        if (ei) {
            int v = edge[ei].to;
            se[top] = edge[ei].nxt;
            first_[v] = etcnt; et_[etcnt] = v; det_[etcnt] = dep[v]; etcnt++;
            sn[++top] = v; se[top] = head[v];
        } else {
            --top;
            if (top) { et_[etcnt] = sn[top]; det_[etcnt] = dep[sn[top]]; etcnt++; }
        }
    }
    for (int i = 0; i < etcnt; ++i) st_[0][i] = i;
    for (int k = 1; (1 << k) <= etcnt; ++k)
        for (int i = 0; i + (1 << k) <= etcnt; ++i) {
            int a = st_[k - 1][i], b = st_[k - 1][i + (1 << (k - 1))];
            st_[k][i] = (det_[a] <= det_[b]) ? a : b;
        }
}
static inline int lca(int x, int y) {
    int l = first_[x], r = first_[y];
    if (l > r) { int t = l; l = r; r = t; }
    int k = 31 - __builtin_clz((unsigned)(r - l + 1));
    int a = st_[k][l], b = st_[k][r - (1 << k) + 1];
    return det_[a] <= det_[b] ? et_[a] : et_[b];
}

static struct { int x, y; ll v; } q_[MAXM + 5];

static struct { int nxt, d; ll v1, v2; } ch_[MAXM * 2 + 5];
static int ch_head[MAXN], ch_cnt;
static inline void addChain(int node, int d, ll v1, ll v2) {
    ch_[++ch_cnt] = {ch_head[node], d, v1, v2};
    ch_head[node] = ch_cnt;
}
static struct { int nxt, idx; } pn_[MAXM + 5];
static int pn_head[MAXN], pn_cnt;
static inline void addPath(int node, int idx) { pn_[++pn_cnt] = {pn_head[node], idx}; pn_head[node] = pn_cnt; }

// ---------- segment tree merge (case 1) ----------
struct SegNode { ll V1, V2; int ch[2]; };
static SegNode seg[4000000];
static int reuse_[4000000];
static int seg_tot, reuse_tot;

static inline int newNode() {
    if (reuse_tot) {
        int id = reuse_[--reuse_tot];
        seg[id].V1 = seg[id].V2 = NEG; seg[id].ch[0] = seg[id].ch[1] = 0;
        return id;
    }
    ++seg_tot;
    seg[seg_tot].V1 = seg[seg_tot].V2 = NEG; seg[seg_tot].ch[0] = seg[seg_tot].ch[1] = 0;
    return seg_tot;
}
static void segInsert(int &rt, int pos, ll v1, ll v2, int l, int r) {
    if (!rt) rt = newNode();
    if (l == r) {
        if (v1 > seg[rt].V1) seg[rt].V1 = v1;
        if (v2 > seg[rt].V2) seg[rt].V2 = v2;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) segInsert(seg[rt].ch[0], pos, v1, v2, l, mid);
    else segInsert(seg[rt].ch[1], pos, v1, v2, mid + 1, r);
    seg[rt].V1 = seg[seg[rt].ch[0]].V1 > seg[seg[rt].ch[1]].V1 ? seg[seg[rt].ch[0]].V1 : seg[seg[rt].ch[1]].V1;
    seg[rt].V2 = seg[seg[rt].ch[0]].V2 > seg[seg[rt].ch[1]].V2 ? seg[seg[rt].ch[0]].V2 : seg[seg[rt].ch[1]].V2;
}
static void segErase(int &rt, int pos, int l, int r) {
    if (!rt) return;
    if (l == r) { reuse_[reuse_tot++] = rt; rt = 0; return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) segErase(seg[rt].ch[0], pos, l, mid);
    else segErase(seg[rt].ch[1], pos, mid + 1, r);
    if (!seg[rt].ch[0] && !seg[rt].ch[1]) { reuse_[reuse_tot++] = rt; rt = 0; }
    else {
        seg[rt].V1 = seg[seg[rt].ch[0]].V1 > seg[seg[rt].ch[1]].V1 ? seg[seg[rt].ch[0]].V1 : seg[seg[rt].ch[1]].V1;
        seg[rt].V2 = seg[seg[rt].ch[0]].V2 > seg[seg[rt].ch[1]].V2 ? seg[seg[rt].ch[0]].V2 : seg[seg[rt].ch[1]].V2;
    }
}
static void segMerge(int &x, int y, ll &t, int l, int r) {
    if (!y) return;
    if (!x) { x = y; return; }
    int xl = seg[x].ch[0], xr = seg[x].ch[1];
    int yl = seg[y].ch[0], yr = seg[y].ch[1];
    if (l == r) {
        if (seg[y].V1 > seg[x].V1) seg[x].V1 = seg[y].V1;
        if (seg[y].V2 > seg[x].V2) seg[x].V2 = seg[y].V2;
        reuse_[reuse_tot++] = y; return;
    }
    ll tmp = seg[xl].V2 + seg[yr].V1; if (tmp > t) t = tmp;
    tmp = seg[xr].V1 + seg[yl].V2; if (tmp > t) t = tmp;
    reuse_[reuse_tot++] = y;
    int mid = (l + r) >> 1;
    segMerge(xl, yl, t, l, mid);
    segMerge(xr, yr, t, mid + 1, r);
    seg[x].ch[0] = xl; seg[x].ch[1] = xr;
    ll v1 = seg[xl].V1, v2 = seg[xl].V2;
    if (seg[xr].V1 > v1) v1 = seg[xr].V1;
    if (seg[xr].V2 > v2) v2 = seg[xr].V2;
    seg[x].V1 = v1; seg[x].V2 = v2;
}
static int Rt[MAXN], maxd_;

static void solveT() {
    for (int idx = n; idx >= 1; --idx) {
        int x = ord_[idx];
        Rt[x] = 0;
        ll t = NEG;
        for (int ei = head[x]; ei; ei = edge[ei].nxt) {
            int v = edge[ei].to;
            if (v == par[x]) continue;
            segMerge(Rt[x], Rt[v], t, 0, maxd_);
        }
        for (int ci = ch_head[x]; ci; ci = ch_[ci].nxt) {
            int rt = 0;
            segInsert(rt, ch_[ci].d, ch_[ci].v1, ch_[ci].v2, 0, maxd_);
            segMerge(Rt[x], rt, t, 0, maxd_);
        }
        ll cand = t - D[x];
        if (cand > ans) ans = cand;
        if (dep[x] > 0) segErase(Rt[x], dep[x] - 1, 0, maxd_);
    }
}

// ---------- virtual tree + diameter merge (case 2) ----------
static int o_[MAXM * 4 + 10];
static int nf[MAXM * 2 + 10]; static ll nD[MAXM * 2 + 10];
static int whead[MAXN], wnext[MAXM * 2 + 10];
static int vis[MAXN];
static int anc[MAXM * 4], vstk[MAXM * 4], px[MAXM * 4], py[MAXM * 4];
static ll tt[MAXM * 4];

static inline bool cmpDfn(int a, int b) { return tin_[a] < tin_[b]; }
static inline ll disAP(int x, int y) {
    if (!x || !y) return NEG;
    return nD[x] + nD[y] - 2 * D[lca(nf[x], nf[y])];
}
static inline void mergeDiam(int &x, int &y, int a, int b, ll &t) {
    ll d1 = disAP(x, a), d2 = disAP(x, b), d3 = disAP(y, a), d4 = disAP(y, b);
    if (d1 > t) t = d1;
    if (d2 > t) t = d2;
    if (d3 > t) t = d3;
    if (d4 > t) t = d4;
    ll p1 = disAP(x, y), p2 = disAP(a, b);
    if (p2 >= p1 && p2 >= d1 && p2 >= d2 && p2 >= d3 && p2 >= d4) { x = a; y = b; return; }
    if (p1 >= d1 && p1 >= d2 && p1 >= d3 && p1 >= d4) return;
    if (d1 >= d2 && d1 >= d3 && d1 >= d4) y = a;
    else if (d2 >= d3 && d2 >= d4) y = b;
    else if (d3 >= d4) x = a;
    else x = b;
}
static void vtree(int *o, int c) {
    sort(o + 1, o + c + 1, cmpDfn);
    int nc = 0;
    for (int i = 1; i <= c; ++i) if (i == 1 || o[i] != o[i - 1]) o[++nc] = o[i];
    c = nc;
    for (int i = 1; i <= c; ++i) vis[o[i]] = 1;
    for (int i = 1; i < c; ++i) {
        int k = lca(o[i], o[i + 1]);
        if (!vis[k]) { vis[k] = 1; o[++nc] = k; }
    }
    sort(o + 1, o + nc + 1, cmpDfn);
    c = 0;
    for (int i = 1; i <= nc; ++i) if (i == 1 || o[i] != o[i - 1]) o[++c] = o[i];
    int T = 0;
    vstk[++T] = 1;
    for (int i = 2; i <= c; ++i) {
        while (tout_[o[vstk[T]]] < tin_[o[i]]) --T;
        anc[i] = vstk[T];
        vstk[++T] = i;
    }
    for (int i = 1; i <= c; ++i) { tt[i] = NEG; px[i] = 0; py[i] = 0; }
    for (int i = c; i > 1; --i) {
        for (int j = whead[o[i]]; j; j = wnext[j]) mergeDiam(px[i], py[i], j, 0, tt[i]);
        ll cand = (tt[i] - 2 * D[o[i]]) >> 1;
        if (cand > ans) ans = cand;
        mergeDiam(px[anc[i]], py[anc[i]], px[i], py[i], tt[anc[i]]);
    }
    for (int i = 1; i <= c; ++i) {
        vis[o[i]] = 0; anc[i] = 0; px[i] = 0; py[i] = 0; tt[i] = 0; whead[o[i]] = 0;
    }
}
static void solveV() {
    for (int x = 1; x <= n; ++x) {
        if (!pn_head[x]) continue;
        int c = 0;
        for (int pi = pn_head[x]; pi; pi = pn_[pi].nxt) {
            int idx = pn_[pi].idx;
            int qx = q_[idx].x, qy = q_[idx].y;
            ll val = 2 * (D[qx] + D[qy] - D[x] - q_[idx].v);
            ++c; o_[c] = qx; nf[c] = qy; nD[c] = val;
            wnext[c] = whead[qx]; whead[qx] = c;
            ++c; o_[c] = qy; nf[c] = qx; nD[c] = val;
            wnext[c] = whead[qy]; whead[qy] = c;
        }
        vtree(o_, c);
        pn_head[x] = 0;
    }
}

// ---------- I/O ----------
static const char *ip, *ipend;
static inline ll rd() {
    while (ip < ipend && (*ip < '0' || *ip > '9')) ++ip;
    ll x = 0;
    while (ip < ipend && *ip >= '0' && *ip <= '9') x = x * 10 + (*ip++ - '0');
    return x;
}
static inline char *wr(char *o, ll x) {
    if (x == ANS_INIT) { *o++ = 'F'; *o++ = '\n'; return o; }
    if (x < 0) { *o++ = '-'; x = -x; }
    char t[24]; int k = 0;
    if (!x) t[k++] = '0';
    while (x) { t[k++] = (char)('0' + x % 10); x /= 10; }
    while (k) *o++ = t[--k];
    *o++ = '\n';
    return o;
}

int main() {
    seg[0].V1 = seg[0].V2 = NEG; seg[0].ch[0] = seg[0].ch[1] = 0;
    seg_tot = 0; reuse_tot = 0;
    struct DuckInfo *di = (struct DuckInfo *)getauxval(0x6b637564UL);
    static char local_in[1 << 22], local_out[1 << 22];
    char *obuf;
    int is_judge = 0;
    if (di && di->stdin_ptr && di->stdin_size) { ip = di->stdin_ptr; ipend = ip + di->stdin_size; obuf = di->stdout_ptr; is_judge = 1; }
    else { size_t z = fread(local_in, 1, sizeof(local_in), stdin); ip = local_in; ipend = ip + z; obuf = local_out; }
    char *o = obuf;
    int T = rd();
    while (T--) {
        n = rd();
        ecnt = 0;
        for (int i = 1; i <= n; ++i) { head[i] = 0; ch_head[i] = 0; pn_head[i] = 0; par[i] = 0; }
        for (int i = 1; i < n; ++i) { int a = rd(), b = rd(); ll c = rd(); addEdge(a, b, c); addEdge(b, a, c); }
        buildTree();
        buildEuler();
        maxd_ = 0;
        for (int i = 1; i <= n; ++i) if (dep[i] > maxd_) maxd_ = dep[i];
        m = rd();
        ch_cnt = 0; pn_cnt = 0;
        for (int i = 1; i <= m; ++i) {
            int x = rd(), y = rd(); ll v = rd();
            q_[i].x = x; q_[i].y = y; q_[i].v = v;
            int z = lca(x, y);
            addPath(z, i);
            if (x != z) addChain(x, dep[z], D[x] + D[y] - D[z] - v, D[x] + D[y] - 2 * D[z] - v);
            if (y != z) addChain(y, dep[z], D[x] + D[y] - D[z] - v, D[x] + D[y] - 2 * D[z] - v);
        }
        ans = ANS_INIT;
        solveT();
        solveV();
        o = wr(o, ans);
    }
    if (is_judge) {
        di->stdout_size = (uint64_t)(o - obuf);
        __asm__ volatile("mov $60, %%eax; xor %%edi, %%edi; syscall" ::: "rax", "rdi", "memory");
        __builtin_unreachable();
    }
#ifdef LOCAL
    fwrite(obuf, 1, o - obuf, stdout);
#endif
    return 0;
}

评测结果