【HDU】5293 Tree chain problem【DP+LCA】

传送门：【HDU】5293 Tree chain problem

my  code:

/*************************************************************************
    > File Name: F.cpp
    > Author: poursoul
    > Created Time: 2015年07月22日 星期三 10时39分49秒
 ************************************************************************/

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000") 
using namespace std ;

typedef long long LL ;
typedef long long Int ;
typedef pair < int , int > pi ;

#define clr(a,x) memset ( a , x , sizeof a ) 

const int MAXN =  ;
const int MAXE =  ;

struct Edge {
    int v , n ;
    Edge () {}
    Edge ( int v , int n ) : v ( v ) , n ( n ) {}
} ;

struct Node {
    int u , v , c ;
    Node () {}
    Node ( int u , int v , int c ) : u ( u ) , v ( v ) , c ( c ) {}
} ;

vector < Node > G[MAXN] ;

Edge E[MAXE] ;
int H[MAXN] , cntE ;

int sum[MAXN] ;
int dep[MAXN] ;
int top[MAXN] ;
int pos[MAXN] ;
int pre[MAXN] ;
int siz[MAXN] ;
int son[MAXN] ;
int dfs_clock ;
int in[MAXN] ;
int ou[MAXN] ;
int tree_idx ;
int dp[MAXN] ;
int n , m ;

void init () {
    cntE =  ;
    tree_idx =  ;
    dfs_clock =  ;
    clr ( H , - ) ;
    clr ( sum ,  ) ;
}

void addedge ( int u , int v ) {
    E[cntE] = Edge ( v , H[u] ) ;
    H[u] = cntE ++ ;
}

void dfs ( int u ) {
    siz[u] =  ;
    son[u] =  ;
    in[u] = ++ dfs_clock ;
    for ( int i = H[u] ; ~i ; i = E[i].n ) {
        int v = E[i].v ;
        if ( v == pre[u] ) continue ;
        dep[v] = dep[u] +  ;
        pre[v] = u ;
        dfs ( v ) ;
        siz[u] += siz[v] ;
        if ( siz[son[u]] < siz[v] ) son[u] = v ;
    }
    ou[u] = dfs_clock ;
}

void rebuild ( int u , int top_element ) {
    top[u] = top_element ;
    pos[u] = ++ tree_idx ;
    if ( son[u] ) rebuild ( son[u] , top_element ) ;
    for ( int i = H[u] ; ~i ; i = E[i].n ) {
        int v = E[i].v ;
        if ( v != pre[u] && v != son[u] ) rebuild ( v , v ) ;
    }
}

int LCA ( int x , int y ) {
    while ( top[x] != top[y] ) dep[top[x]] < dep[top[y]] ? ( y = pre[top[y]] ) : ( x = pre[top[x]] ) ;
    return dep[x] < dep[y] ? x : y ;
}

void add ( int x , int v ) {
    for ( ; x <= n ; x += x & -x ) sum[x] += v ;
}

int query ( int x , int ans =  ) {
    for ( ; x >  ; x -= x & -x ) ans += sum[x] ;
    return ans ;
}

void getdp ( int u ) {
    dp[u] =  ;
    for ( int i = H[u] ; ~i ; i = E[i].n ) {
        int v = E[i].v ;
        if ( v == pre[u] ) continue ;
        getdp ( v ) ;
        dp[u] += dp[v] ;
    }
    add ( in[u] , dp[u] ) ;
    add ( ou[u] +  , -dp[u] ) ;
    int tmp =  ;
    for ( int i =  ; i < G[u].size () ; ++ i ) {
        int x = G[u][i].u ;
        int y = G[u][i].v ;
        int c = G[u][i].c ;
        tmp = max ( tmp , c + query ( in[x] ) + query ( in[y] ) - dp[u] ) ;
    }
    dp[u] = max ( dp[u] , tmp ) ;
    add ( in[u] , -dp[u] ) ;
    add ( ou[u] +  , dp[u] ) ;
}


void scanf ( int& x , char c =  ) {
    while ( ( c = getchar () ) < '0' ) ;
    x = c - '0' ;
    while ( ( c = getchar () ) >= '0' ) x = x *  + c - '0' ;
}

void solve () {
    int u , v , c ;
    init () ;
    scanf ( n ) ;
    scanf ( m ) ;
    for ( int i =  ; i <= n ; ++ i ) {
        G[i].clear () ;
    }
    for ( int i =  ; i < n ; ++ i ) {
        scanf ( u ) ;
        scanf ( v ) ;
        addedge ( u , v ) ;
        addedge ( v , u ) ;
    }
    dfs (  ) ;
    rebuild (  ,  ) ;
    for ( int i =  ; i <= m ; ++ i ) {
        scanf ( u ) ;
        scanf ( v ) ;
        scanf ( c ) ;
        G[LCA ( u , v )].push_back ( Node ( u , v , c ) ) ;
    }
    getdp (  ) ;
    printf ( "%d\n" , dp[] ) ;
}

int main () {
    int T ;
    scanf ( "%d" , &T ) ;
    for ( int i =  ; i <= T ; ++ i ) {
        solve () ;
    }
    return  ;
}