Tree chain problem

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 262    Accepted Submission(s): 59

1

7 3

1 2

1 3

2 4

2 5

3 6

3 7

2 3 4

4 5 3

6 7 3

6

Hint

 Stack expansion program： #pragma comment(linker, "/STACK:1024000000,1024000000") 

题目大意：有一颗n个节点的数。给出n-1条边(无向)，还有m条链，每条链链接两个顶点(按lca的方式链接)。链存在一个权值w。如今想要挑选一些链，挑选的链中不能出现同样的节点，问能够挑选出的最大的权重是多少？

要求权值最大，依照树形dp的思路去考虑，那么dp[i]为以第i个点位根节点的子树的最优解。dp[i]的状态转移公式，有两种可能，第一种：第i个节点上不出现链，那么dp[i] = ∑(dp[k] | k为i的子节点)；另外一种：第i个节点上出现链。假设选择增加这条链，那么dp[i] = w(链的权值) + ∑(dp[k] | k为链上的节点的子节点) = w + ∑(sum[k]
| k为链上的节点 ) - ∑(dp[k] | k为链上的节点) 。sum[i]表示i节点的全部子节点的dp和，在 ∑(sum[k] | k为链上的节点 ) - ∑(dp[k] | k为链上的节点) 中减去的dp[k]会由它的父节点的sum补全。

这样就得到了状态转移公式。

还有要计算给出的链的两个顶点的lca(用于更新dp的值)，在更新dp值的时候须要计算链上节点的(sun的和)(dp的和)，使用树状数组来计算。对全部节点进行dfs。对点进行又一次编号。每到达一个点和每离开一个点都要编号，记录在l[i]和r[i]中，当计算玩一个sum[i]值后。加到树状数组c1中(l[i]位置加正值，r[i]位置加负值)。计算完一个dp[i]值后，加到树状数组c2中(l[i]位置加正值，r[i]位置加负值)。依照新的编号进行树状数组计算区间和。也就能够得到链上的节点的和

总结：

1、建树，题目给出的(无向边)。要加双边

2、dfs，建立rmq[i][j]：i节点的第2^j个父节点，对节点又一次编号

3、对给出的两个顶点求lca。(代码中用rmq求lca)

4、树状数组，求区间和。

5、深搜，完毕树形dp，按状态转移方程计算每个节点的值，使用树状数组计算链上节点的和

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std ;

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

#define maxn 200050

struct E{

    int v , next ;

}edge[maxn] ;

int head[maxn] , cnt ;

struct node{

    int u , v , w ;

    int lca ;

}p[maxn] ;

int dep[maxn] , rmq[maxn][20] ;

int l[100010] , r[maxn] , cid ;

vector <int> vec[maxn] ;

int dp[maxn] , sum[maxn] ;

int c1[maxn] , c2[maxn] ;

void add_E(int u,int v) {

    edge[cnt].v = v ;

    edge[cnt].next = head[u] ; head[u] = cnt++ ;

    edge[cnt].v = u ;

    edge[cnt].next = head[v] ; head[v] = cnt++ ;

}

void dfs(int fa,int u) {

    l[u] = ++cid ;

    int i , j , v ;

    for(i = head[u] ; i != -1 ; i = edge[i].next) {

        v = edge[i].v ;

        if( v == fa ) continue ;

        dep[v] = dep[u] + 1 ;

        rmq[v][0] = u ;

        for(j = 1 ; j < 20 ; j++)

            rmq[v][j] = rmq[ rmq[v][j-1] ][j-1] ;

        dfs(u,v) ;

    }

    r[u] = ++cid ;

}

int lca(int u,int v) {

    if( dep[u] < dep[v] )

        swap(u,v) ;

    int i , j ;

    for(i = 19 ; i >= 0 ; i--) {

        if( dep[ rmq[u][i] ] >= dep[v] )

            u = rmq[u][i] ;

        if( u == v ) return u ;

    }

    for(i = 19 ; i >= 0 ; i--) {

        if( rmq[u][i] != rmq[v][i] ){

            u = rmq[u][i] ;

            v = rmq[v][i] ;

        }

    }

    return rmq[u][0] ;

}

int lowbit(int x) {

    return  x & -x ;

}

void add(int i,int k,int *c,int n) {

    while( i <= n ) {

        c[i] += k ;

        i += lowbit(i) ;

    }

}

int getsum(int i,int *c) {

    int ans = 0 ;

    while( i ) {

        ans += c[i] ;

        i -= lowbit(i) ;

    }

    return ans ;

}

void solve(int fa,int s,int n) {

    dp[s] = sum[s] = 0 ;

    int i , j , u , v , temp ;

    for(i = head[s] ; i != -1 ;i = edge[i].next) {

        v = edge[i].v ;

        if( v == fa ) continue ;

        solve(s,v,n) ;

        sum[s] += dp[v] ;

    }

    dp[s] = sum[s] ;

    for(i = 0 ; i < vec[s].size() ; i++) {

        u = p[ vec[s][i] ].u ;

        v = p[ vec[s][i] ].v ;

        temp = getsum(l[u],c1) + getsum(l[v],c1) - getsum(l[u],c2) - getsum(l[v],c2) + sum[s] ;

        dp[s] = max(dp[s],temp+p[vec[s][i]].w) ;

    }

    add(l[s],sum[s],c1,n*2) ;

    add(r[s],-sum[s],c1,n*2) ;

    add(l[s],dp[s],c2,n*2) ;

    add(r[s],-dp[s],c2,n*2) ;

}

void init(int n) {

    memset(head,-1,sizeof(head)) ;

    memset(rmq,0,sizeof(rmq)) ;

    memset(c1,0,sizeof(c1)) ;

    memset(c2,0,sizeof(c2)) ;

    cnt = cid = 0 ;

    dep[1] = 1 ;

    rmq[1][0] = 1  ;

    for(int i = 1 ; i <= n ; i++)

        vec[i].clear() ;

    return ;

}

int main() {

    int t , n , m ;

    int i , j , u , v , w ;

    //freopen("1006.in","r",stdin) ;

    //freopen("t.out","w",stdout) ;

    scanf("%d", &t) ;

    while( t-- ) {

        scanf("%d %d", &n, &m) ;

        init(n) ;

        for(i = 1 ; i < n ; i++) {

            scanf("%d %d", &u, &v) ;

            add_E(u,v) ;

        }

        dfs(-1,1) ;

        for(i = 0 ; i < m ; i++) {

            scanf("%d %d %d", &p[i].u, &p[i].v, &p[i].w) ;

            p[i].lca = lca(p[i].u,p[i].v) ;

            vec[ p[i].lca ].push_back(i) ;

        }

        solve(-1,1,n) ;

        printf("%d\n", dp[1]) ;

    }

    return 0 ;

}