poj 1741 （点分治入门）
09年漆子超论文第一题。
点分治，关键是重心的性质。定义：在一棵树上找到一点u使得删除u后所有分开的子树中size最大的子树最小，则u为重心。其性质是所有分开的子树的size必然不超过(N/2)，那么就可以做到nlogn了。这题还有排序这部分，所以整体复杂度是nlog(n)log(n)。
代码:
#include #include #include #include #include #include #include #include #define ll __int64 #define lson l , m , rt << 1 #define rson m + 1 , rt << 1 | 1 #define new_edge(a,b,c) edge[tot].t = b , edge[tot].v = c , edge[tot].next = head[a] , head[a] = tot ++ using namespace std; const int maxn = 11111 ; struct Edge { int t , next ; ll v ; } edge[maxn<<1] ; int head[maxn] , vis[maxn] , tot , k ; int temp , mdp[maxn] , dp[maxn] ; ll que[maxn] , tail , ans , dis[maxn] ; int cnt_son ( int u , int fa ) { int i ; mdp[u] = dp[u] = 0 ; que[++tail] = u ; for ( i = head[u] ; i != -1 ; i = edge[i].next ) { int e = edge[i].t ; if ( e == fa || vis[e] ) continue ; cnt_son ( e , u ) ; dp[u] += dp[e] , mdp[u] = max ( mdp[u] , dp[e] ) ; } return ++ dp[u] ; } int get ( int u ) { int temp = maxn , ret ; tail = 0 ; cnt_son ( u , u ) ; while ( tail ) { int e = que[tail--] ; int fuck = max ( mdp[e] , dp[u] - dp[e] ) ; if ( fuck < temp ) temp = fuck , ret = e ; } return ret ; } void add ( int u , int fa ) { int i ; que[++tail] = dis[u] ; for ( i = head[u] ; i != -1 ; i = edge[i].next ) { int e = edge[i].t ; if ( e == fa || vis[e] ) continue ; dis[e] = dis[u] + edge[i].v ; add ( e , u ) ; } } ll cal ( ll v ) { ll ret = 0 , i ; for ( i = 1 ; i < tail ; i ++ ) { while ( i < tail && que[i] + que[tail] > k- 2 * v ) tail -- ; ret += tail - i ; } return ret ; } void dfs ( int u ) { int cg = get ( u ) , i ; u = cg ; tail = 0 ; dis[u] = 0 ; add ( u , u ) ; sort ( que + 1 , que + tail + 1 ) ; ll k = cal ( 0 ) , j = 0 ; vis[u] = 1 ; for ( i = head[u] ; i != -1 ; i = edge[i].next ) { int e = edge[i].t ; if ( vis[e] ) continue ; tail = 0 ; dis[e] = 0 ; add ( e , e ) ; sort ( que + 1 , que + tail + 1 ) ; j += cal ( edge[i].v ) ; } ans += k - j ; for ( i = head[u] ; i != -1 ; i = edge[i].next ) { int e = edge[i].t ; if ( vis[e] ) continue ; dfs ( e ) ; } } void init () { memset ( head , -1 , sizeof ( head ) ) ; memset ( vis , 0 , sizeof ( vis ) ) ; tot = ans = 0 ; } int main() { int n , i , j ; while ( scanf ( "%d%d" , &n , &k ) != EOF ) { if ( n == 0 && k == 0 ) break ; init () ; for ( i = 1 ; i < n; i ++ ) { int a , b ; ll c ; scanf ( "%d%d%I64d" , &a , &b , &c ) ; new_edge ( a , b , c ) ; new_edge ( b , a , c ) ; } dfs ( 1 ) ; printf ( "%I64d\n" , ans ) ; } return 0; } /* 5 4 1 2 3 1 3 1 1 4 2 3 5 1 5 4 1 2 3 1 3 3 1 4 2 5 3 1 5 4 1 2 3 1 3 2 1 4 2 5 3 1 0 0 */