P5642 人造情感（emotion）

link

考虑 \(W(U)\) 怎么求。

定义 \(f_x\) 表示只考虑所有在 \(x\) 子树内的路径时最大收益，\(sum_x\) 为只考虑 \(x\) 子树中路径，且钦定 \(x\) 不选的最大收益。

\(g\) 的转移显然：\(g_x=\sum f_{to}\)

\(f\) 转移考虑枚举 \(\text{lca}=x\) 的所有路径 \((u,v,w)\)，有：\(f_x\longleftarrow\sum\limits_{i}(sum_i-f_i)+w\)，其中 \(i\) 为 \((u,v,w)\) 上的所有点。树状数组优化可做到 \(O(n\log n)\)。

换根，\(h_x\) 表示强制 \(x\to fa_x\) 边不能经过，此时最大收益。

考虑怎么从 \(h_x\) 推到 \(h_{to}\)。

一种是直接强制 \(x\) 不能选，即 \(h_{to}\longleftarrow h_x-f_x+sum_x\)；

一种考虑枚举一条经过 \(x\) 路径 \((u,v,w)\)，强制选该路径。此时会对该链的邻域以 \(h_x+\sum\limits_{i}(sum_i-f_i)+w\) 的收益更新。

注意到这个权值与更新的目标无关，于是可以将路径按照收益从大往小排序。

\(x\) 子节点 \(to\) 更新可以直接暴力找到第一条 \(u,v\) 不在 \(to\) 子树中的路径，因为每条路径只会被跳过 \(2\) 次，该部分为线性。

对于不为 \(x\) 子节点的 \(to\)，考虑在 \(u,v\) 处分别记录 \((u,v,w)\) 和其收益。

每次只需查询 \(fa_{to}\) 子树除掉 \(to\) 子树外的最大收益，可以线段树维护。

现在有了 \(f,sum,h\)，考虑求答案。

对于一对 \(u,v\)，假设其 \(\text{lca}=x\)，强制选择后总收益为 \(h_x+\sum\limits_{i}(sum_x-f_x)\)。最小的 \(w\) 即为 \(W(U)\) 减去该值，可以拆贡献计算。

#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[r] + 1
using namespace std;
void file() {
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
}
using ll = long long;
using i128 = __int128_t;
template <typename T> using vec = vector<T>;

const int mod = 998244353;

const int nLim = 3e5 + 5, kLim = 1.2e6 + 5;
int n, m, o;
array<int, nLim> siz, fa, dfn, tl, tr, dep;
array<ll, nLim> f, sum, h, pre;
array<array<int, nLim>, 20> mn;
array<vec<int>, nLim> g, id;

struct path {
  int u, v; ll w;
  path(int _u, int _v, ll _w) {
    u = _u; v = _v; w = _w;
  }
};
array<vec<path>, nLim> paths;

void dfs(int x, int Fa) {
  fa[x] = Fa; siz[x] = 1;
  dep[x] = dep[Fa] + 1;
  id[dep[x]].push_back(x);
  mn[0][tl[x] = dfn[x] = ++o] = Fa;
  for(int to : g[x])
    if(to ^ Fa) {
      dfs(to, x);
      siz[x] += siz[to];
    }
  tr[x] = o;
}

int mindfn(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
void init() {
  for(int i = 1; i < 20; i++)
    for(int l = 1, r = (1 << i); r <= n; l++, r++)
      mn[i][l] = mindfn(mn[i - 1][l], mn[i - 1][l + (1 << i - 1)]);
}
int lca(int x, int y) {
  if(x == y) return x;
  if((x = dfn[x]) > (y = dfn[y])) swap(x, y);
  int p = __lg(y - x++);
  return mindfn(mn[p][x], mn[p][y - (1 << p) + 1]);
}

struct BIT {
  array<ll, nLim> tr;
  void update(int x, ll v) {
    for(; x <= n; x += (x & -x)) tr[x] += v;
  }
  ll query(int x) {
    ll res = 0;
    for(; x; x -= (x & -x)) res += tr[x];
    return res;
  }
  void update(int l, int r, ll v) {
    update(l, v); update(r + 1, -v);
  }
}bit;

void dfs2(int x, int Fa) {
  for(int to : g[x])
    if(to ^ Fa) {
      dfs2(to, x);
      sum[x] += f[to];
    }
  f[x] = sum[x];
  for(path k : paths[x])
    f[x] = max(f[x], k.w + bit.query(dfn[k.u]) + bit.query(dfn[k.v]) + sum[x]);
  bit.update(tl[x], tr[x], sum[x] - f[x]);
}

void dfs3(int x, int Fa) {
  pre[x] = pre[Fa] + sum[x] - f[x];
  for(int to : g[x])
    if(to ^ Fa) dfs3(to, x);
}

bool isanc(int x, int y) { return (tl[x] <= dfn[y]) && (tr[x] >= dfn[y]); }

#define ls (o << 1)
#define rs (o << 1 | 1)

struct SGT {
  array<ll, kLim> mx;
  void pu(int o) { mx[o] = max(mx[ls], mx[rs]); }
  void update(int o, int l, int r, int x, ll v) {
    if(l == r) return void(mx[o] = max(mx[o], v));
    int mi = (l + r) >> 1;
    (mi < x) ? update(rs, mi + 1, r, x, v) : update(ls, l, mi, x, v);
    pu(o);
  }
  ll query(int o, int l, int r, int x, int y) {
    if((l > y) || (r < x)) return 0;
    if((l >= x) && (r <= y)) return mx[o];
    int mi = (l + r) >> 1;
    return max(query(ls, l, mi, x, y), query(rs, mi + 1, r, x, y));
  }
}sgt;

int32_t main() {
  // file();
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  for(int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0); init();
  for(int i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w;
    paths[lca(u, v)].emplace_back(u, v, w);
  }
  dfs2(1, 0); dfs3(1, 0); h[1] = f[1];
  for(int d = 2; d <= n; d++) {
    for(int x : id[d - 1]) {
      for(auto& k : paths[x])
        k.w += pre[k.u] + pre[k.v] - pre[x] - pre[fa[x]];
      sort(ALL(paths[x]), [&](path x, path y) { return x.w > y.w; });
      for(int to : g[x]) {
        if(fa[to] != x) continue;
        h[to] = h[x] - f[x] + sum[x];
        h[to] = max(h[to], sgt.query(1, 1, n, tl[x], tl[to] - 1));
        h[to] = max(h[to], sgt.query(1, 1, n, tr[to] + 1, tr[x]));
        for(path k : paths[x])
          if(!isanc(to, k.u) && !isanc(to, k.v)) {
            h[to] = max(h[to], h[x] + k.w);
            break;
          }
      }
    }
    for(int x : id[d - 1])
      for(path k : paths[x]) {
        sgt.update(1, 1, n, dfn[k.u], h[x] + k.w);
        sgt.update(1, 1, n, dfn[k.v], h[x] + k.w);
      }
  }
  ll all = f[1], res = (i128)all * n * n % mod;
  for(int i = 1; i <= n; i++)
    res = (res - (i128)pre[i] * 2 * n % mod + mod) % mod;
  for(int i = 1; i <= n; i++) {
    ll s = 0;
    for(int to : g[i])
      if(fa[to] == i) s += (ll)siz[to] * siz[to];
    res = (res - (i128)(h[i] - pre[i] - pre[fa[i]]) * ((ll)siz[i] * siz[i] - s) % mod + mod) % mod;
  }
  cout << res << "\n";
  return 0;
}