代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <map>
#include <cctype>
const int MAXN = 5e4 + 10;
const int MAXM = 1e5 + 10;
typedef long long LL;
const LL INF = 1e18;

struct Edge {
  int v, w, next;
}edge[MAXN << 1];
int head[MAXN], tail = 1;
int weight[MAXN];
int x[MAXM], y[MAXM];
LL v[MAXM];
int n, m;
void insert(int u, int v, int w) {
  edge[++tail] = (Edge) {v, w, head[u]}; head[u] = tail;
}
namespace io{
  const int SIZE = 1e6;
  char buff[SIZE];
  char *l, *r;
  void init() {
    l = buff;
    r = l + fread(buff, 1, SIZE, stdin);
  }
  char gc() {
    if (l == r) init();
    return *(l++);
  }
  template <class T> inline
  void read(T &x) {
    x = 0; char ch = gc();
    while(!isdigit(ch)) ch = gc();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
  }
} using io::read;
namespace solver1 {

  namespace calc_lca {
    int dep[MAXN], sz[MAXN], top[MAXN], fa[MAXN], son[MAXN];
    LL len[MAXN];
    void dfs(int u, int f) {
      dep[u] = dep[f] + 1;
      fa[u] = f;
      int max_son = 0;
      sz[u] = 1;
      
      for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        len[v] = len[u] + edge[i].w;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] > max_son) {
          max_son = sz[v];
          son[u] = v;
        }
      }
    }
    void dfs2(int u, int t) {
      top[u] = t;
      if (son[u]) {
        dfs2(son[u], t);
      }
      for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == son[u]) continue;
        dfs2(v, v);
      }
    }
    void init() {
      std::fill(son + 1, son + n, 0);
      dfs(1, 0);
      dfs2(1, 1);
    }
    int lca(int x, int y) {
      while(top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
        x = fa[top[x]];
      }
      return dep[x] < dep[y] ? x : y;
    }
  }using calc_lca::lca; using calc_lca::len; using calc_lca::dep;
  LL ans, delta;
  void chk_ans(LL val) {
    ans = std::max(ans, val + delta);
  }
  struct Data {
    typedef std::pair<int, LL> Pii;
    Pii p1, p2;
    LL ans;
    Data (): p1({-1, -1}), p2({-1, -1}), ans(-INF) {}
    Data (int p, LL val): p1({p, val}), p2({-1, -1}), ans(-INF)  {}
    LL calc(Pii p1, Pii p2) {
      if (p1.first == -1 || p2.first == -1) return -INF;
      int l = lca(p1.first, p2.first);
      return p1.second + p2.second + len[p1.first] + len[p2.first] - 2 * len[l];
    }
    void merge(const Data& rhs, const LL det) {
      if (p1.first == -1) { *this = rhs; return; }
      if (rhs.p1.first == -1) return;
      
      Pii _p1 = p1, _p2 = p2; LL t;
      delta = det;
      if (rhs.ans > ans) {
        ans = rhs.ans;
        _p1 = rhs.p1;
        _p2 = rhs.p2;
      }

      if ((t = calc(p1, rhs.p1)) > ans) {
        ans = t;
        _p1 = p1;
        _p2 = rhs.p1;
      }
      chk_ans(t);
        
      if ((t = calc(p1, rhs.p2)) > ans) {
        ans = t;
        _p1 = p1;
        _p2 = rhs.p2;
      }
      chk_ans(t);
  
      if ((t = calc(p2, rhs.p1)) > ans) {
        ans = t;
        _p1 = p2;
        _p2 = rhs.p1;
      }
      chk_ans(t);
      
      if ((t = calc(p2, rhs.p2)) > ans) {
        ans = t;  
        _p1 = p2;
        _p2 = rhs.p2;
      }
      chk_ans(t);
      
      p1 = _p1;
      p2 = _p2;
    }
  };
  namespace seg_tree {
    const int SIZE = 5e6;
    struct Node {
      int ls, rs;
      LL max1, max2;
    }tree[SIZE];
    int root[MAXN], cnt;
    int newnode() {
      int u = ++cnt;
      tree[u].ls = tree[u].rs = 0;
      tree[u].max1 = tree[u].max2 = -INF;
      return u;
    }
    void init() {
      std::fill(root + 1, root + n + 1, 0);
      cnt = -1;
      newnode();
    }
    void update(int node) {
      Node &u = tree[node];
      u.max1 = std::max(tree[u.ls].max1, tree[u.rs].max1);
      u.max2 = std::max(tree[u.ls].max2, tree[u.rs].max2);
    }
    void _merge(int &x, int y, int l, int r, LL left, LL right) {
      if (!y) return;
      if (!x) {
        x = y;
        chk_ans((tree[y].max1 + right) * 2);
        chk_ans((tree[y].max2 + left) * 2);
        return;
      }
      if (l == r) {
        tree[x].max1 = std::max(tree[x].max1, tree[y].max1);
        tree[x].max2 = std::max(tree[x].max2, tree[y].max2);
        chk_ans((tree[y].max1 + right) * 2);
        chk_ans((tree[y].max2 + left) * 2);
        return;
      }

      int mid = (l + r) >> 1;
      LL nl = std::max(tree[tree[x].ls].max1, left);
      _merge(tree[x].ls, tree[y].ls, l, mid, left, std::max(tree[tree[x].rs].max2, right));
      _merge(tree[x].rs, tree[y].rs, mid + 1, r, nl, right);
      update(x);
    }
    void merge(int x, int y, LL det) {
      delta = det;
      _merge(root[x], root[y], 1, n, -INF, -INF);
    }
    int p;
    LL val1, val2;
    LL left, right;
    void _insert(int &node, int l, int r) {
      if (!node) node = newnode();
      if (l == r) {
        tree[node].max1 = std::max(tree[node].max1, val1);
        tree[node].max2 = std::max(tree[node].max2, val2);
        chk_ans((left + val2) * 2);
        chk_ans((right + val1) * 2);
        return;
      }
      int mid = (l + r) >> 1;
      if (p <= mid) {
        right = std::max(tree[tree[node].rs].max2, right);
        _insert(tree[node].ls, l, mid);
      } else {
        left = std::max(tree[tree[node].ls].max1, left);
        _insert(tree[node].rs, mid + 1, r);
      }
      update(node);
    }
    void insert(int x, int y, LL v1, LL v2, LL det) {
      val1 = v1, val2 = v2, p = y;
      left = right = -INF;
      delta = det;
      
      _insert(root[x], 1, n);

    }

    void _remove(int node, int l, int r) {
      if (!node) return;
      if (l == r) {
        tree[node].max1 = tree[node].max2 = -INF;
        return;
      }
      int mid = (l + r) >> 1;
      if (p <= mid) _remove(tree[node].ls, l, mid);
      else _remove(tree[node].rs, mid + 1, r);
      update(node);
    }
    void remove(int x, int y) {
      p = y;
      _remove(root[x], 1, n);
    }
    void _print(int node, int l, int r) {
      if (!node) return;
      if (l == r) {
        fprintf(stderr, "[%d]: max1 = %lld, max2 = %lld\n", l, tree[node].max1, tree[node].max2);
        return;
      }
      int mid = (l + r) >> 1;
      _print(tree[node].ls, l, mid);
      _print(tree[node].rs, mid + 1, r);
    }
    void print(int x) {
      fprintf(stderr, "Tree %d:\n", x);
      _print(root[x], 1, n);
    }
  }
  std::map<int, Data> f[MAXN];
  
  void dfs(int u) {
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v;
      //fprintf(stderr, "%d %d\n", u, v);
      dfs(v);
      
      seg_tree::remove(v, dep[u]);
      seg_tree::merge(u, v, -len[u] * 2);
      //ans = std::max(ans, (seg_tree::merge(u, v) - len[u]) * 2);
      //fprintf(stderr, "%d %d(1): %lld\n", u, v, ans);
      if (f[u].size() < f[v].size()) f[u].swap(f[v]);

      for (auto j: f[v]) {
        if (dep[j.first] >= dep[u]) continue;
        f[u][j.first].merge(j.second, -len[u] * 2);
        //ans = std::max(ans, f[u][j.first].ans - len[u] * 2);
      }
      f[u].erase(u);
      //fprintf(stderr, "%d %d(2): %lld\n", u, v, ans);
    }
  }
  void main() {
    calc_lca::init();
    for (int i = 1; i <= n; i++) {
      f[i].clear();
    }

    seg_tree::init();
    ans = -INF;    
    for (int i = 1; i <= m; i++) {
      int l = lca(x[i], y[i]);
      //fprintf(stderr, "%d\n", l);
      LL dist = len[x[i]] + len[y[i]] - len[l] * 2;
      if (x[i] != l) {
        f[x[i]][l].merge(Data({y[i], dist + len[x[i]] - 2 * v[i]}), -len[x[i]] * 2);
        //ans = std::max(ans, f[x[i]][l].ans - len[x[i]] * 2);
        //ans = std::max((seg_tree::insert(x[i], dep[l], dist - v[i], dist - v[i] + len[l]) - len[x[i]]) * 2, ans);
        seg_tree::insert(x[i], dep[l], dist - v[i], dist - v[i] + len[l], -len[x[i]] * 2);
      }
      
      if (y[i] != l) {
        f[y[i]][l].merge(Data({x[i], dist + len[y[i]] - 2 * v[i]}), -len[y[i]] * 2);
        //ans = std::max(ans, f[y[i]][l].ans - len[y[i]] * 2);
        //ans = std::max((seg_tree::insert(y[i], dep[l], dist - v[i], dist - v[i] + len[l]) - len[y[i]]) * 2, ans);
        seg_tree::insert(y[i], dep[l], dist - v[i], dist - v[i] + len[l], -len[y[i]] * 2);
      }
    }

    //fprintf(stderr, "%lld\n", ans);
    dfs(1);

    if (ans < (-INF / 2)) puts("F");
    else printf("%lld\n", ans / 2);
    
    
  }
}
int main() {
  //freopen("center.in", "r", stdin);
  //freopen("center.out", "w", stdout);
  int t;
  //scanf("%d", &t);
  read(t);
  while(t--) {
    //scanf("%d", &n);
    //fprintf(stderr, "?");
    read(n);
    std::fill(head + 1, head + n + 1, 0);
    tail = 1;

    for (int i = 1; i < n; i++) {
      int u, v, w;
      //scanf("%d%d%d", &u, &v, &w);
      read(u);
      read(v);
      read(w);
      insert(u, v, w);
    }

    //scanf("%d", &m);
    read(m);
    for (int i = 1; i <= m; i++) {
      //scanf("%d%d%lld", x + i, y + i, v + i);
      read(x[i]), read(y[i]), read(v[i]);
    }

    solver1::main();
  }
}

评测结果