注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-2783: [JLOI2012]树  

2014-02-12 20:07:00|  分类: oi,bzoj,dfs,set, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2783


赤裸裸的水题,DFS一遍SET维护即可。


代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
 
using namespace std ;
 
#define ll long long
#define MAXN 100100
 
struct node {
    int k , cnt ;
    node(  ) {
        cnt = 0 ;
    }
    node( int _k , int _cnt ) : k( _k ) , cnt( _cnt ) {
         
    }
    bool operator < ( const node &a ) const {
        return k < a.k ;
    }
    bool operator == ( const node &a ) const {
        return k == a.k ;
    }
    bool operator > ( const node &a ) const {
        return k > a.k ;
    }
};
set < node > bst ;
 
struct edge {
    edge *next ;
    int t ;
} *head[ MAXN ] ;
 
void AddEdge( int s , int t ) {
    edge *p = new( edge ) ;
    p -> t = t , p -> next = head[ s ] ;
    head[ s ] = p ;
}
 
int n , len , w[ MAXN ] , roof ;
bool f[ MAXN ] ; 
ll ans = 0 ;
 
void dfs( int v , int sum ) {
    sum += w[ v ] ;
    set < node > :: iterator i = bst.find( node( sum - len , 0 ) ) ;
    if ( i != bst.end(  ) ) ans += ( ll )( i -> cnt ) ;
    i = bst.find( node( sum , 0 ) ) ;
    if ( i == bst.end(  ) ) bst.insert( node( sum , 1 ) ) ; else {
        node ret = *i ;
        bst.erase( i ) ;
        bst.insert( ret ) ;
    }
    for ( edge *p = head[ v ] ; p ; p = p -> next ) {
        dfs( p -> t , sum ) ;
    }
    i = bst.find( node( sum , 0 ) ) ;
    if ( i -> cnt == 1 ) bst.erase( i ) ; else {
        node ret = *i ;
        -- ret.cnt ;
        bst.erase( i ) ;
        bst.insert( ret ) ;
    }
}
 
int main(  ) {
    scanf( "%d%d" , &n , &len ) ;
    for ( int i = 0 ; i ++ < n ; ) scanf( "%d" , w + i ) ;
    memset( f , true , sizeof( f ) ) ;
    for ( int i = 1 ; i < n ; ++ i ) {
        int s , t ; scanf( "%d%d" , &s , &t ) ;
        AddEdge( s , t ) , f[ t ] = false ;
    }
    for ( int i = 0 ; i ++ < n ; ) if ( f[ i ] ) roof = i ;
    bst.clear(  ) ;
    bst.insert( node( 0 , 1 ) ) ;
    dfs( roof , 0 ) ;
    printf( "%lld\n" , ans ) ;
    return 0 ;
}



  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018