传送门

题目大意：

一颗n个点的树，给出m条链，第i条链的权值是\(w_i\)，可以选择若干条不相交的链，求最大权值和。

题目分析：

树型dp: dp[u][0]表示不经过u节点，其子树的最优值，dp[u][1]表示考虑经过u节点该子树的最优值（可能过，可能不过），很明显：$$dp[u][0] = \sum{max(dp[v][0], dp[v][1])} v是u的儿子$$, 下面来算dp[u][1]: 考虑一条经过u（以u为lca）的链，他经过子树中的节点v(可能有多个)，那么$$dp[u][1] = dp[u][0] + w_i + max{-max(dp[v][0], dp[v][1]) + dp[v][0]}$$减去max(dp[v][0], dp[v][1])是因为我们更新dp[u][0]时取得是两者较大值，而此时需要减去的其实是dp[v][1]，如果取较大值减去了dp[v][0],然后加上dp[v][0]就等于没减，没有影响，而若减去dp[v][1],然后加上dp[v][0]，则刚好达到目的。

现在来考虑怎么求该链上的dp值：有两种方法

• 树链剖分 + 线段树 + dp： 链剖以便求lca和区间求和，在lca节点放入这条链，扫描完子树后（dfs子树完便得到dp[u][0]），处理以该节点u为lca的链x->y，将链拆成两条：x->u和u->y,另tmp = dp[u][0]，\(tmp -= queryMaxDp0Dp1Sum(x, u), tmp += queryDp0Sum(x, u)\) 另一条链同理，处理完后，dp[u][1] = max(dp[u][1], tmp + \(w_i\));
  
  处理完这些链后，将u节点的dp值插入链剖线段树中，并更新答案。总复杂度为\(n log^2n\)

• 树状数组 + dp： 会快一点，但不会。

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

#include<set>

#include<cmath>

using namespace std;

namespace IO{

    inline int read(){

        int i = 0, f = 1; char ch = getchar();

        for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

        if(ch == '-') f = -1, ch = getchar();

        for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');

        return i * f;

    }

    inline void wr(int x){

        if(x < 0) putchar('-'), x = -x;

        if(x > 9) wr(x / 10);

        putchar(x % 10 + '0');

    }

}using namespace IO;

const int N = 1e5 + 5, M = 1e5 + 5, OO = 0x3f3f3f3f;

int n, m, top[N], son[N], pos[N], tot, dep[N], fa[N], sze[N];

vector<int> G[N];

typedef long long ll;

ll ans, dp[N][2];

struct node{int u, v; ll val;};

vector<node> chainThrough[N];

namespace SegTree{

    ll sum[N << 2], maxSum[N << 2];

    inline void insert(int k, int l, int r, int pos, ll v, ll *t){

        if(l == r){t[k] = v; return;}

        int mid = (l + r) >> 1;

        if(pos <= mid) insert(k << 1, l, mid, pos, v, t);

        else insert(k << 1 | 1, mid + 1, r, pos, v, t);

        t[k] = t[k << 1] + t[k << 1 | 1];

    }

    inline ll query(int k, int l, int r, int x, int y, ll *t){

        if(x == l && r == y) return t[k];

        int mid = (l + r) >> 1;

        ll ret = 0;

        // if(x <= mid) ret += query(k << 1, l, mid, x, y, t);

        // if(y > mid) ret += query(k << 1 | 1, mid + 1, r, x, y, t);

        // return ret;

        if(y <= mid) return query(k << 1, l, mid, x, y, t);

        else if(x > mid) return query(k << 1 | 1, mid + 1, r, x, y, t);

        else return query(k << 1, l, mid, x, mid, t) + query(k << 1 | 1, mid + 1, r, mid + 1, y, t);

    }

}using namespace SegTree;

inline void dfs1(int u, int f){

    dep[u] = dep[f] + 1, fa[u] = f, sze[u] = 1;

    for(int e = G[u].size() - 1; e >= 0; e--){

        int v = G[u][e];

        if(v == f) continue;

        dfs1(v, u), sze[u] += sze[v];

        if(sze[v] > sze[son[u]]) son[u] = v;

    }

}

inline void dfs2(int u, int f){

    if(son[u]){

        pos[son[u]] = ++tot;

        top[son[u]] = top[u];

        dfs2(son[u], u);

    }

    for(int e = G[u].size() - 1; e >= 0; e--){

        int v = G[u][e];

        if(v == f || v == son[u]) continue;

        pos[v] = ++tot;

        top[v] = v;

        dfs2(v, u);

    }

}

inline int getLca(int u, int v){

    while(top[u] != top[v]){

        if(dep[top[u]] < dep[top[v]]) swap(u, v);

        u = fa[top[u]];

    }

    return dep[u] < dep[v] ? u : v;

}

inline ll pathQuery(int u, int v, ll *t){

    ll ret = 0;

    while(top[u] != top[v]){

        if(dep[top[u]] < dep[top[v]]) swap(u, v);

        ret += query(1, 1, n, pos[top[u]], pos[u], t);

        u = fa[top[u]];

    }

    if(dep[u] > dep[v]) swap(u, v);

    return ret + query(1, 1, n, pos[u], pos[v], t);

}

inline void DP(int u, int f){

    for(int e = G[u].size() - 1; e >= 0; e--){

        int v = G[u][e];

        if(v == f) continue;

        DP(v, u), dp[u][0] += max(dp[v][0], dp[v][1]);

    }

    for(int i = 0; i < chainThrough[u].size(); i++){

        int x = chainThrough[u][i].u, y = chainThrough[u][i].v;

        ll tmp = dp[u][0];

        if(dep[x] > dep[u]) tmp += pathQuery(x, u, sum), tmp -= pathQuery(x, u, maxSum);

        if(dep[y] > dep[u]) tmp += pathQuery(y, u, sum), tmp -= pathQuery(y, u, maxSum);

        dp[u][1] = max(dp[u][1], tmp + chainThrough[u][i].val);

    }

    insert(1, 1, n, pos[u], dp[u][0], sum);

    insert(1, 1, n, pos[u], max(dp[u][1], dp[u][0]), maxSum);

    ans = max(ans, max(dp[u][0], dp[u][1]));

}

inline void splitTree(){

    tot = 1, pos[1] = 1, top[1] = 1;

    dfs1(1, 0), dfs2(1, 0);

}

int T;

int main(){

    T = read();

    while(T--){

        n = read(), m = read();

        for(int i = 1; i <= n; i++) G[i].clear(), chainThrough[i].clear(), ans = 0;

        memset(sze, 0, sizeof sze), memset(dep, 0, sizeof dep), memset(son, 0, sizeof son);

        memset(sum, 0, sizeof sum), memset(maxSum, 0, sizeof maxSum), memset(dp, 0, sizeof dp);

        for(int i = 1; i < n; i++){int u = read(), v = read(); G[u].push_back(v), G[v].push_back(u);}

        splitTree();

        for(int i = 1; i <= m; i++){int u = read(), v = read(); ll val = read()*1ll; chainThrough[getLca(u, v)].push_back((node){u, v, val});}

        DP(1, 0);

        // for(int i=1;i<=n;i++)for(int j=0;j<chainThrough[i].size();j++)cout<<i<<" "<<chainThrough[i][j].u<<" "<<chainThrough[i][j].v<<" "<<endl;

        wr(ans), putchar('\n');

    }

    return 0;

}