代码

// NOI2018 情报中心 (duck.ac noi18e)
// Algorithm: segment-tree merge (different apexes) + virtual tree / diameter merge (same apex).
// O(m log n + m log m). All tree traversals are iterative (no deep recursion).
#include <bits/stdc++.h>
#include <sys/auxv.h>
#include <stdint.h>
#include <unistd.h>
using namespace std;
typedef long long ll;

struct DuckInfo {
  uint64_t abi_version;
  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_frequency;
} __attribute__((packed));

static const char *inp, *inp_end;
static char FI[1 << 20], *FA = FI, *FB = FI;
static inline int gc() {
  if (FA == FB) { FB = (FA = FI) + fread(FI, 1, sizeof(FI), stdin); if (FA == FB) return EOF; }
  return (unsigned char)*FA++;
}
static inline ll rd() {
  if (inp) {
    while (inp < inp_end && (*inp < '0' || *inp > '9')) ++inp;
    ll x = 0;
    while (inp < inp_end && *inp >= '0' && *inp <= '9') { x = x * 10 + (*inp - '0'); ++inp; }
    return x;
  }
  int c = gc();
  while (c != EOF && (c < '0' || c > '9')) c = gc();
  ll x = 0;
  while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
  return x;
}

const int MAXN = 50005;
const int MAXM = 100005;
const int LG = 17;
const ll NEG = -(1LL << 60);
const ll ANS_INIT = -(1LL << 59);

int n, m;
ll ans;

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

int up[MAXN][LG + 1], dep[MAXN];
ll D[MAXN];
int tin[MAXN], tout[MAXN];
int ord[MAXN], ordcnt;
int stk_[MAXN], stk_top;

void buildTree() {
  up[1][0] = 0; dep[1] = 0; D[1] = 0;
  ordcnt = 0; stk_top = 1; stk_[1] = 1;
  while (stk_top) {
    int x = stk_[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 == up[x][0]) continue;
      up[v][0] = x;
      dep[v] = dep[x] + 1;
      D[v] = D[x] + edge[ei].w;
      stk_[++stk_top] = v;
    }
  }
  for (int i = 1; i <= n; ++i) tout[ord[i]] = tin[ord[i]];
  for (int i = n; i >= 2; --i) {
    int x = ord[i], p = up[x][0];
    if (tout[x] > tout[p]) tout[p] = tout[x];
  }
  for (int i = 1; i <= LG; ++i)
    for (int x = 1; x <= n; ++x)
      up[x][i] = up[up[x][i - 1]][i - 1];
}

inline int lca(int a, int b) {
  if (dep[a] < dep[b]) { int t = a; a = b; b = t; }
  int diff = dep[a] - dep[b];
  for (int i = 0; diff; ++i, diff >>= 1) if (diff & 1) a = up[a][i];
  if (a == b) return a;
  for (int i = LG; i >= 0; --i) if (up[a][i] != up[b][i]) { a = up[a][i]; b = up[b][i]; }
  return up[a][0];
}

// ---------- Queries ----------
struct Query { int x, y; ll v; } q[MAXM + 5];

// case 1: chains (apex depth d, values v1,v2) attached at endpoint node
struct Chain { int nxt, d; ll v1, v2; };
Chain ch[MAXM * 2 + 5];
int ch_head[MAXN], ch_cnt;
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;
}

// case 2: paths attached at apex node
struct PathNode { int nxt, idx; };
PathNode pn[MAXM + 5];
int pn_head[MAXN], pn_cnt;
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];
int seg_tot, reuse_tot;

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;
}

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 = max(seg[seg[rt].ch[0]].V1, seg[seg[rt].ch[1]].V1);
  seg[rt].V2 = max(seg[seg[rt].ch[0]].V2, seg[seg[rt].ch[1]].V2);
}

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 = max(seg[seg[rt].ch[0]].V1, seg[seg[rt].ch[1]].V1);
    seg[rt].V2 = max(seg[seg[rt].ch[0]].V2, seg[seg[rt].ch[1]].V2);
  }
}

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;
}

int Rt[MAXN];

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 == up[x][0]) continue;
      segMerge(Rt[x], Rt[v], t, 0, n);
    }
    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, n);
      segMerge(Rt[x], rt, t, 0, n);
    }
    ll cand = t - D[x];
    if (cand > ans) ans = cand;
    if (dep[x] > 0) segErase(Rt[x], dep[x] - 1, 0, n);
  }
}

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

inline bool cmpDfn(int a, int b) { return tin[a] < tin[b]; }

inline ll disAP(int x, int y) {
  if (!x || !y) return NEG;
  return nD[x] + nD[y] - 2 * D[lca(nf[x], nf[y])];
}

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;
}

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;
  }
}

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;
  }
}

// ---------- Main ----------

int main() {
  DuckInfo *duck = (DuckInfo *)getauxval(0x6b637564);
  if (duck && duck->stdin_ptr) { inp = duck->stdin_ptr; inp_end = inp + duck->stdin_size; }
  else { inp = nullptr; }
  seg[0].V1 = seg[0].V2 = NEG; seg[0].ch[0] = seg[0].ch[1] = 0;
  seg_tot = 0; reuse_tot = 0;

  int T = (int)rd();
  while (T--) {
    n = (int)rd();
    ecnt = 0;
    for (int i = 1; i <= n; ++i) { head[i] = 0; ch_head[i] = 0; pn_head[i] = 0; up[i][0] = 0; }
    for (int i = 1; i < n; ++i) {
      int a = (int)rd(), b = (int)rd(); ll c = rd();
      addEdge(a, b, c); addEdge(b, a, c);
    }
    buildTree();
    m = (int)rd();
    ch_cnt = 0; pn_cnt = 0;
    for (int i = 1; i <= m; ++i) {
      int x = (int)rd(), y = (int)rd(); ll v = rd();
      q[i] = {x, y, 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();
    if (ans == ANS_INIT) puts("F");
    else printf("%lld\n", ans);
  }

  return 0;
}

评测结果