[HDU5293] Tree chain problem(트리 DP, 트리 배열)

Description

한 그루의 나무와 많은 체인을 정하면 모든 체인은 가치가 있고 서로 교차하지 않는 체인을 선택하여 가치와 최대를 요구한다.

Solution

dp[u]dp[u]를 서브 트리 u 내의 답안으로 설정하고sum[u]=∑v∈children(u)dp[v]sum[u]=∑v v i l d r e n(u)d p [v]를 설정합니다.LCA에서 각 체인의 처리를 고려합니다.uu에 있는 LCA의 모든 체인을 선택하지 않으면 dp[u]=sum[u] d p [u] = s u m [u]입니다.그 다음에 모든 LCA가 uuu의 체인,chkmax(dp[u],val+∑sum[v]--∑dp[v])chkmax(dp[u],val+∑sum[v]--∑dp[v])(그중 v매거체인의 각 점)을 매거한다.그 중에서 ∑sum[v] ∑s um[v], ∑dp[v] ∑dp[v]는 두 그루의 나무상수조로 유지하면 된다.

Solution

/************************************************
 * Au: Hany01
 * Date: Sep 4th, 2018
 * Prob: HDU5293 Tree chain problem
 * Email: [email protected] & [email protected]
 * Inst: Yali High School
************************************************/

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
#include

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(), a.end()
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read() {
    static int _, __; static char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}

const int maxn = 1e5 + 5;

int n, m, beg[maxn], nex[maxn << 1], v[maxn << 1], fa[19][maxn], e, dp[maxn], sum[maxn], dep[maxn], dfn[maxn], efn[maxn], clk;
vectorint> > qry[maxn];

struct FenwickTree {
    int c[maxn];
    inline void update(int x, int dt) { for ( ; x <= n; x += (x & -x)) c[x] += dt; }
    inline void update(int l, int r, int dt) { update(l, dt), update(r + 1, -dt); }
    inline int  query(int x) { static int ans; for (ans = 0; x; x -= (x & -x)) ans += c[x]; return ans; }
}Tsum, Tdp;

inline void add(int uu, int vv) { v[++ e] = vv, nex[e] = beg[uu], beg[uu] = e; }

void Init(int u, int pa) {
    fa[0][u] = pa, dep[u] = dep[pa] + 1, dfn[u] = ++ clk;
    For(i, 1, 18) fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (register int i = beg[u]; i; i = nex[i])
        if (v[i] != pa) Init(v[i], u);
    efn[u] = clk;
}

inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    Fordown(i, 18, 0) if (dep[fa[i][u]] >= dep[v]) u = fa[i][u];
    if (u == v) return u;
    Fordown(i, 18, 0) if (fa[i][u] != fa[i][v]) u = fa[i][u], v = fa[i][v];
    return fa[0][u];
}

void DFS(int u, int pa) {
    sum[u] = 0;
    for (register int i = beg[u]; i; i = nex[i])
        if (v[i] != pa) DFS(v[i], u), sum[u] += dp[v[i]];
    Tsum.update(dfn[u], efn[u], dp[u] = sum[u]);
    rep(i, SZ(qry[u])) {
        register int x = qry[u][i].x.x, y = qry[u][i].x.y;
        chkmax(dp[u], Tsum.query(dfn[x]) + Tsum.query(dfn[y]) - Tsum.query(dfn[u]) - Tsum.query(dfn[pa])
        - Tdp.query(dfn[x]) - Tdp.query(dfn[y]) + Tdp.query(dfn[u]) + Tdp.query(dfn[pa]) + qry[u][i].y);
    }
    Tdp.update(dfn[u], efn[u], dp[u]), qry[u].clear();
}

int main()
{
#ifdef hany01
    freopen("hdu5293.in", "r", stdin);
    freopen("hdu5293.out", "w", stdout);
#endif

    for (static int T = read(), uu, vv, ww; T --; ) {
        n = read(), m = read(), e = 1, clk = 0, Set(beg, 0);
        For(i, 2, n) uu = read(), vv = read(), add(uu, vv), add(vv, uu);
        Init(1, 0), Set(Tsum.c, 0), Set(Tdp.c, 0);
        For(i, 1, m) uu = read(), vv = read(), ww = read(), qry[LCA(uu, vv)].push_back(mp(mp(uu, vv), ww));
        DFS(1, 0), printf("%d
", dp[1]);
    }

    return 0;
}