Switching activity estimation is a crucial step in estimating dynamic power consumption in CMOS circuits. In [1] , we proposed a new switching probability model based on Bayesian Networks which captures accurately the various correlations in the circuit. In this work, we propose a new strategy for efficient segmentation of large circuits so that they can be mapped to Multiple Bayesian Networks (MBN). The goal here is to achieve higher accuracy while reducing the memory requirements during the computation. In order to capture the correlations among the boundaries of segments, a tree-dependent (TD) distribution is proposed between the segment boundaries such that the TD distribution is closest to the actual distribution of switching variable with some distance criterion. We use a Maximum Weight Spanning Tree (MWST) based approximation [4] using mutual information between two variables at the boundary as weight of the edge between the variables. Experimental results for ISCAS'85 circuits show that the proposed method improves accuracy significantly over other methods.