BZOJ 1782: [Usaco2010 Feb]slowdown 慢慢游( BIT + dfs )

时间：2015-06-07 15:47:47 阅读：209 评论：0 收藏：0 [点我收藏+]

技术分享

orz...hzwer 对着大神的 code 看 , 稍微理解了.

考虑一只牛到达 , 那它所在子树全部 +1 , 可以用BIT维护

-----------------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<vector>

#define rep( i , n ) for( int i = 0 ; i < n ; i++ )

#define clr( x , c ) memset( x , c , sizeof( x ) )

#define Rep( i , n ) for( int i = 1 ; i <= n ; ++i )

using namespace std;

const int maxn = 100000 + 5;

vector< int > G[ maxn ];

void add_edge( int u , int v ) {

G[ u ].push_back( v );

G[ v ].push_back( u );

}

int b[ maxn ];

int n;

void init() {

rep( i , n )

G[ i ].clear();

}

#define lowbit( x ) ( x & -x )

void update( int x , int v ) {

for( ; x <= n ; x += lowbit( x ) )

b[ x ] += v;

}

int query( int x ) {

int res = 0;

for( ; x ; x -= lowbit( x ) )

res += b[ x ];

return res;

}

int ans[ maxn ];

int pos[ maxn ];

void dfs( int x , int fa ) {

ans[ pos[ x ] ] = query( pos[ x ] );

update( pos[ x ] , 1 );

rep( i , G[ x ].size() ) {

int to = G[ x ][ i ];

if( to == fa ) continue;

dfs( to , x );

}

update( pos[ x ] , -1 );

}

int main() {

freopen( "test.in" , "r" , stdin );

cin >> n;

rep( i , n - 1 ) {

int u , v;

scanf( "%d%d" , &u , &v );

u-- , v--;

add_edge( u , v );

}

Rep( i , n ) {

int t;

scanf( "%d" , &t );

--t;

pos[ t ] = i;

}

dfs( 0 , -1 );

Rep( i , n )

printf( "%d\n" , ans[ i ] );

return 0;

}

-----------------------------------------------------------------------

1782: [Usaco2010 Feb]slowdown 慢慢游

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 574 Solved: 350
[Submit][Status][Discuss]

Description

每天Farmer John的N头奶牛(1 <= N <= 100000，编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在1号牧场。恰好有N-1条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第i条路连接着A_i，B_i，(1 <= A_i <= N; 1 <= B_i <= N)。奶牛们每人有一个私人牧场P_i (1 <= P_i <= N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛1离开，前往P_1；然后是奶牛2，以此类推。当奶牛i走向牧场P_i时候，他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时，奶牛i会放慢自己的速度，防止打扰他的朋友。考虑如下的牧场结构（括号内的数字代表了牧场的所有者）。技术分享