题目分析:遇到和树有关的肯定先dfs,首先将美味值离散化(反正所有的都不相同,随便离散),然后按照题目给的树dfs,顺便记录其时间戳用以求前两个答案,因为dfs走的恰好是从根到一个点的路径,所以在dfs是顺带用树状数组维护果实的个数,答案三就是查询前面添加的果实有多少比当前的大就行了。
接下来把果实按照美味值从大到小排序(其实还是同一个比较函数,到过来读取就行了),每次为这个果实 u 查找子树区间[ in[ u ] , ou[ u ] ]内有多少比他大就好了,这个是答案一,然后答案二就等于n - fruit[ u ].x(x为离散后的)-答案一。
是不是很简单?就是我写的比较搓,跑的很慢。
代码如下:
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #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 travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next ) #define CLR( a , x ) memset ( a , x , sizeof a ) #define CPY( a , x ) memcpy ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define mid ( ( l + r ) >> 1 ) #define root 1 , 1 , n #define rt o , l , r const int MAXN = 100005 ; const int MAXE = 100005 ; struct Edge { int v ; Edge* next ; } E[MAXE] , *H[MAXN] , *cur ; struct Node { int x , idx ; } fruit[MAXN] ; int in[MAXN] , ou[MAXN] , dfs_clock ; int ans1[MAXN] , ans2[MAXN] , ans3[MAXN] ; int T[MAXN] ; int n ; int cmp1 ( const Node& a , const Node& b ) { return a.x < b.x ; } int cmp2 ( const Node& a , const Node& b ) { return a.idx < b.idx ; } void add ( int x , int v ) { while ( x ) { T[x] += v ; x -= x & -x ; } } int sum ( int x , int ans = 0 ) { if ( !x ) return 0 ; while ( x <= n ) { ans += T[x] ; x += x & -x ; } return ans ; } void clear () { cur = E ; dfs_clock = 0 ; CLR ( H , 0 ) ; CLR ( T , 0 ) ; } void addedge ( int u , int v ) { cur -> v = v ; cur -> next = H[u] ; H[u] = cur ++ ; } void dfs ( int u ) { in[u] = ++ dfs_clock ; ans3[u] = sum ( fruit[u].x ) ; add ( fruit[u].x , 1 ) ; travel ( e , H , u ) dfs ( e -> v ) ; add ( fruit[u].x , -1 ) ; ou[u] = dfs_clock ; } void solve () { int x ; clear () ; scanf ( "%d" , &n ) ; FOR ( i , 2 , n ) { scanf ( "%d" , &x ) ; addedge ( x , i ) ; } FOR ( i , 1 , n ) { scanf ( "%d" , &fruit[i].x ) ; fruit[i].idx = i ; } sort ( fruit + 1 , fruit + n + 1 , cmp1 ) ; FOR ( i , 1 , n ) fruit[i].x = i ; sort ( fruit + 1 , fruit + n + 1 , cmp2 ) ; dfs ( 1 ) ; sort ( fruit + 1 , fruit + n + 1 , cmp1 ) ; CLR ( T , 0 ) ; REV ( i , n , 1 ) { int idx = fruit[i].idx ; //printf ( "%d %d\n" , ou[idx] , in[idx] - 1 ) ; ans1[idx] = sum ( in[idx] ) - sum ( ou[idx] + 1 ) ; ans2[idx] = n - fruit[i].x - ans1[idx] ; add ( in[idx] , 1 ) ; } FOR ( i , 1 , n ) printf ( "%d %d %d\n" , ans1[i] , ans2[i] , ans3[i] ) ; } int main () { freopen ( "treesfruits.in" , "r" , stdin ) ; freopen ( "treesfruits.out" , "w" , stdout ) ; solve () ; }