本文主要是介绍【codeforces】293E. Close Vertices 点分治+树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【codeforces】293E. Close Vertices
题目分析：找一棵树上有多少条路径长度不超过l且边权和不超过w的路径。
我们用点分治处理。
分治每一层，对每一个重心，预处理出到重心距离d，边权和为w的所有路径。将路径按照w排序，然后我们用双指针扫描数组，同时维护一个树状数组，树状数组中保存的是到重心距离为d的条数。因为有贡献可能来自子树，于是我们对子树进行同样的操作去重。注意不要忘记到重心的符合条件的路径的计数。
做这题的时候犯了一些逗比错误，比如将路径按照w排序后以最后一个元素的d值作为树状数组的大小了= =。
代码如下：
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;
const int MAXE = 200005 ;struct Edge {int v , c , n ;Edge () {}Edge ( int var , int cost , int next ) : v ( var ) , c ( cost ) , n ( next ) {}
} ;struct Node {int w , d ;Node () {}Node ( int w , int d ) : w ( w ) , d ( d ) {}bool operator < ( const Node& a ) const {return w < a.w ;}
} ;Edge E[MAXE] ;
int H[MAXN] , cntE ;
int Q[MAXN] , head , tail ;
bool vis[MAXN] ;
int siz[MAXN] ;
int dis[MAXN] ;
int dep[MAXN] ;
int pre[MAXN] ;
Node node[MAXN] ;
int T[MAXN] , maxdis ;
LL ans ;
int n , w , l ;void clear () {ans = 0 ;cntE = 0 ;clr ( H , -1 ) ;clr ( vis , 0 ) ;
}void addedge ( int u , int v , int c ) {E[cntE] = Edge ( v , c , H[u] ) ;H[u] = cntE ++ ;
}void add ( int x , int v ) {for ( int i = x ; i <= maxdis ; i += i & -i ) T[i] += v ;
}int sum ( int x , int res = 0 ) {for ( int i = x ; i > 0 ; i -= i & -i ) res += T[i] ;return res ;
}int get_root ( int s ) {head = tail = 0 ;pre[s] = 0 ;Q[tail ++] = s ;while ( head != tail ) {int u = Q[head ++] ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( v != pre[u] && !vis[v] ) {pre[v] = u ;Q[tail ++] = v ;}}}int tot_size = tail ;int root = s , max_size = tail ;while ( tail ) {int u = Q[-- tail] ;int cnt = 0 ;siz[u] = 1 ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( v != pre[u] && !vis[v] ) {siz[u] += siz[v] ;cnt = max ( siz[v] , cnt ) ;}}cnt = max ( cnt , tot_size - siz[u] ) ;if ( cnt < max_size ) {max_size = cnt ;root = u ;}}return root ;
}LL get_ans ( int s , int init_dis , int init_dep , bool isroot ) {head = tail = 0 ;int top = 0 ;pre[s] = 0 ;Q[tail ++] = s ;dis[s] = init_dis ;dep[s] = init_dep ;while ( head != tail ) {int u = Q[head ++] ;if ( !isroot || u != s ) node[top ++] = Node ( dis[u] , dep[u] ) ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( v != pre[u] && !vis[v] ) {pre[v] = u ;dis[v] = dis[u] + E[i].c ;dep[v] = dep[u] + 1 ;Q[tail ++] = v ;}}}sort ( node , node + top ) ;LL res = 0 ;int j = top - 1 ;maxdis = 0 ;rep ( i , 0 , top ) if ( node[i].d > maxdis ) maxdis = node[i].d ;For ( i , 1 , maxdis ) T[i] = 0 ;rep ( i , 0 , top ) add ( node[i].d , 1 ) ;if ( isroot ) rep ( i , 0 , top ) if ( node[i].w <= w && node[i].d <= l ) ++ ans ;rep ( i , 0 , top ) {while ( i < j && node[i].w + node[j].w > w ) {add ( node[j].d , -1 ) ;-- j ;}if ( j <= i ) break ;add ( node[i].d , -1 ) ;res += sum ( min ( maxdis , l - node[i].d ) ) ;}return res ;
}void divide ( int u ) {int root = get_root ( u ) ;vis[root] = 1 ;ans += get_ans ( root , 0 , 0 , true ) ;for ( int i = H[root] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( !vis[v] ) ans -= get_ans ( v , E[i].c , 1 , false ) ;}for ( int i = H[root] ; ~i ; i = E[i].n ) if ( !vis[E[i].v] ) divide ( E[i].v ) ;
}void solve () {int x , d ;clear () ;For ( i , 2 , n ) {scanf ( "%d%d" , &x , &d ) ;addedge ( x , i , d ) ;addedge ( i , x , d ) ;}divide ( 1 ) ;printf ( "%I64d\n" , ans ) ;
}int main () {while ( ~scanf ( "%d%d%d" , &n , &l , &w ) ) solve () ;return 0 ;
}这篇关于【codeforces】293E. Close Vertices 点分治+树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
