[BZOJ5210] - 최대 연결 서브 블록 및 - 트리 단면+동적 DP

앞에서 말하다
이해가 안 되는 것 같아서 많은 정의들을 한참을 생각했는데... 결국은 마스터의 코드를 보고 바꿨는데...
제목.
BZOJ5210 전송문 대가 블로그 전송문 보기문제 스탬프 전송문
해법
여기 는 결코 무슨 해법 을 쓸 준비 는 하지 않았는데, 대가 블로그 는 사실 매우 분명하게 썼다. 이해하지 못하면 몇 번 더 읽고 많이 생각해 봐라
이 문제에 대해 me는 유지보수하는 것을 똑똑히 생각해야 할 것 같다...체인에 있는 정보는 직접 라인 트리로 유지보수한다. 실제 답안은 저장되지 않았다.Query가 얻어야 한다.
허위 정보 업로드, 전체 체인이 대표하는 하위 트리의 정보 업로드.한 가지 변화가 생기면 공헌에 변화가 생기기 때문에 이전의 공헌을 취소하고 새로운 공헌으로 바꿔야 한다.공헌이 저장되지 않았기 때문에Query를 통해
초기 상태는 나무를 절단할 때 dp를 한 번 보낸 다음에 dp에서 얻은 정보를 적당한 방식으로 라인 트리에 올리거나 모든 점을 0으로 시작한 다음에 빈 트리에 값을 부여할 수도 있다.물론 이 단계도 0의 값을 보충해야 하는 정보인데 수동 dp의 절차를 생략했을 뿐이다
어차피 잘 생각해야 되는데...

#include 
#include 
#include 
#include 
#include 
#include 
#define QL Query( nd->ch[0] , lf , mid , L , R ) 
#define QR Query( nd->ch[1] , mid+1,rg , L , R ) 
using namespace std ;

int N , M , val[200005] , head[200005] , tp ;
long long g[200005] , f[200005] ;
struct Path{
    int pre , to ;
} p[400005] ;

struct HEap{
    priority_queue<long long,vector<long long>,less<long long> > hp , del ;
    void insert( long long x ){ hp.push( x ) ; }
    void erase( long long x ){ del.push( x ) ; }
    long long top(){
        while( !del.empty() && hp.top() == del.top() )
            hp.pop() , del.pop() ;
        return hp.empty() ? 0 : hp.top() ;
    }
} hp[200005] ;

struct Node{
    Node *ch[2] ;
    long long Lmax , Rmax , mx , sum ;
    void update(){
        Lmax = max( ch[0]->Lmax , ch[0]->sum + ch[1]->Lmax ) ;
        Rmax = max( ch[0]->Rmax + ch[1]->sum , ch[1]->Rmax ) ;
        mx = max( ch[0]->Rmax + ch[1]->Lmax , max( ch[0]->mx , ch[1]->mx ) ) ;
        sum = ch[0]->sum + ch[1]->sum ;
    }
    friend Node Merge( Node L , Node R ){
        Node rt ;
        rt.Lmax = max( L.Lmax , L.sum + R.Lmax ) ;
        rt.Rmax = max( L.Rmax + R.sum , R.Rmax ) ;
        rt.mx = max( L.Rmax + R.Lmax , max( L.mx , R.mx ) ) ;
        rt.sum = L.sum + R.sum ; return rt ;
    }
} *root , w[400005] , *tw = w ;

void In( int t1 , int t2 ){
    p[++tp] = ( Path ){ head[t1] , t2 } ; head[t1] = tp ;
    p[++tp] = ( Path ){ head[t2] , t1 } ; head[t2] = tp ;
}

int dep[200005] , fa[200005] , son[200005] , siz[200005] ;
int in[200005] , top[200005] , arc[200005] , dfs_c , bot[200005] ;
void dfs1( int u ){
    for( int i = head[u] ; i ; i = p[i].pre ){
        int v = p[i].to ;
        if( v == fa[u] ) continue ;
        fa[v] = u , dep[v] = dep[u] + 1 ;
        dfs1( v ) , siz[u] += siz[v] ;
        if( siz[ son[u] ] < siz[v] ) son[u] = v ;
    } siz[u] ++ ;
}

long long dfs2( int u , int topp ){
    long long now = 0 ;
    in[u] = ++dfs_c , arc[ dfs_c ] = u , top[u] = topp ;
    if( son[u] ) now = dfs2( son[u] , topp ) , bot[u] = bot[ son[u] ] ;
    else bot[u] = u ;

    g[u] = val[u] ;
    for( int i = head[u] ; i ; i = p[i].pre ){
        int v = p[i].to ;
        if( v == fa[u] || v == son[u] ) continue ;
        hp[u].insert( dfs2( v , v ) ) , g[u] += f[v] ;
    } f[u] = max( 0ll , g[u] + f[ son[u] ] ) , now = max( now , max( f[u] , hp[u].top() ) ) ;
    return now ;
}

Node *build( int lf , int rg ){
    Node *nd = ++tw ;
    if( lf == rg ){
        int u = arc[lf] ; nd->sum = g[u] ;
        nd->Lmax = nd->Rmax = max( 0ll , g[u] ) ;
        nd->mx = max( nd->Lmax , hp[u].top() ) ;
        return nd ;
    } int mid = ( lf + rg ) >> 1 ;
    nd->ch[0] = build( lf , mid ) ;
    nd->ch[1] = build( mid+1,rg ) ;
    nd->update() ; return nd ;
}

void Modify( Node *nd , int lf , int rg , int pos ){
    if( lf == rg ){
        int u = arc[lf] ; nd->sum = g[u] ;
        nd->Lmax = nd->Rmax = max( 0ll , g[u] ) ;
        nd->mx = max( nd->Lmax , hp[u].top() ) ; return ;
    } int mid = ( lf + rg ) >> 1 ;
    if( mid >= pos ) Modify( nd->ch[0] , lf , mid , pos ) ;
    else Modify( nd->ch[1] , mid+1,rg , pos ) ;
    nd->update() ;
}

Node Query( Node *nd , int lf , int rg , int L , int R ){
    if( L <= lf && rg <= R ) return *nd ;
    int mid = ( lf + rg ) >> 1 ;
    if( R <= mid ) return QL ;
    if( L > mid ) return QR ;
    return Merge( QL , QR ) ;
}

void Modify( int u , long long delta ){
    Node now , pre , ttt ; bool flag = false ;
    while( u ){
        ttt = Query( root , 1 , N , in[ top[u] ] , in[ bot[u] ] ) ;
        if( flag ) hp[u].erase( pre .mx ) , hp[u].insert( now.mx ) ;
        pre = ttt , flag = 1 ;
        g[u] += delta , Modify( root , 1 , N , in[u] ) ;
        now = Query( root , 1 , N , in[ top[u] ] , in[ bot[u] ] ) ;
        delta = now.Lmax - f[ top[u] ] , f[ top[u] ] = now.Lmax ;
        u = fa[ top[u] ] ;
    }
}

long long Query( int u ){
    Node ans = Query( root , 1 , N , in[u] , in[ bot[u] ] ) ;
    return ans.mx ;
}

void preWork(){
    dfs1( 1 ) ; dfs2( 1 , 1 ) ;
    root = build( 1 , N ) ;
}

void solve(){
    char opt[10] ;
    for( int i = 1 , x , y ; i <= M ; i ++ ){
        scanf( "%s%d" , opt , &x ) ;
        if( opt[0] == 'M' ){
            scanf( "%d" , &y ) ;
            Modify( x , y - val[x] ) , val[x] = y ;
        } else printf( "%lld
" , Query( x ) ) ;
    }
}

int main(){
    scanf( "%d%d" , &N , &M ) ;
    for( int i = 1 ; i <= N ; i ++ )
        scanf( "%d" , &val[i] ) ;
    for( int i = 1 , u , v ; i < N ; i ++ )
        scanf( "%d%d" , &u , &v ) , In( u , v ) ;
    preWork() ; solve() ;
}