BZOJ-2809: [Apio2012]dispatching

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2809

题目说的很复杂，说白了就是给你一棵树，然后选出一个节点，在该节点的子树上选取尽可能多的点，并使得选的点的权值和不到于m，明显，这里可以把所有的点取出来，按权值排序，然后从小往大取（调整法可以轻松证明），尽可能取多的点，那么这里就可以先把树处理成DFS序列，然后用主席树维护，直接在主席树上二分即可。

复杂度：O(n log n)

代码：

8326cffc1e178a82028a0fc9f403738da977e821.jpg.png

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define ll long long

#define L( t ) node[ t ].left

#define R( t ) node[ t ].right

#define Sum( t ) node[ t ].sum

#define S( t ) node[ t ].size

#define MAXN 100100

#define MAXV 5000100

 

ll inf = 0x7fffffff;

 

struct edge{

        edge *next ;

        int t ;

}*head[ MAXN ];

 

void AddEdge(int s ,int t ){

        edge *p =new( edge );

        p -> t = t , p -> next = head[ s ];

        head[ s ]= p ;

}

 

struct Node{

        int left , right , size ;

        ll sum ;

        Node (  ){

               left = right = sum = size =0;

        }

} node[ MAXV ];

 

int V =0, n ;

ll m , a[ MAXN ][2];

 

void Add(int l ,int r ,int k , ll v ,int u ,int&t ){

        t =++ V ;

        S( t )=S( u )+1,Sum( t )=Sum( u )+ v ;

        if( l == r )return;

        int mid =( l + r )>>1;

        if( k <= mid )R( t )=R( u ),Add( l , mid , k , v ,L( u ),L( t ));else

        L( t )=L( u ),Add( mid +1, r , k , v ,R( u ),R( t ));

}

 

void Init(  ){

        memset( head ,0,sizeof( head ));

        L(0)=R(0)=S(0)=Sum(0)=0;

        inf *= inf ;

}

 

struct saver{

        ll v ;

        int t ;

        bool operator<(const saver &a )const{

               return v < a.v ;

        }

} b[ MAXN ];

int bn , Rank[ MAXN ];

 

int dfn[ MAXN *2], cnt =0, pre[ MAXN *2], first[ MAXN ], last[ MAXN ];

 

void dfs(int v ){

        dfn[ first[ v ]=++ cnt ]= v ;

        for( edge *p = head[ v ]; p ; p = p -> next )dfs( p -> t );

        dfn[ last[ v ]=++ cnt ]= v ;

}

 

ll ans =0;

 

int main(  ){

        int roof ;

        Init(  );

        scanf("%d%lld",&n ,&m ); m *=2;

        for(int i =0; i ++< n ;){

               int x ;scanf("%d%lld%lld",&x ,&a[ i ][0],&a[ i ][1]);

               if( x )AddEdge( x , i );else roof = i ;

               b[ i ].v = a[ i ][0], b[ i ].t = i ;

        }

        b[ n +1].v =- inf , b[ n +1].t =0, b[ bn = n +2].v = inf , b[ n +2].t =0;

        sort( b +1, b + bn +1);

        for(int i =0; i ++< bn ;) Rank[ b[ i ].t ]= i ;

        pre[0]=0;

        dfs( roof );

        for(int i =0; i ++< cnt ;)Add(1, bn , Rank[ dfn[ i ]], a[ dfn[ i ]][0], pre[ i -1], pre[ i ]);

        for(int i =0; i ++< n ;){

               ll rec = m , num =0;

               int t0 = pre[ first[ i ]-1], t1 = pre[ last[ i ]], l =1, r = bn ;

               while( l < r ){

                       ll ret =Sum(L( t1 ))-Sum(L( t0 ));

                       int mid =( l + r )>>1;

                       if( ret <= rec ){

                               rec -= ret , num +=S(L( t1 ))-S(L( t0 ));

                               t0 =R( t0 ), t1 =R( t1 ), l = mid +1;

                       }else{

                               t0 =L( t0 ), t1 =L( t1 ), r = mid ;

                       }

               }

               ans =max( ans ,( num /2)* a[ i ][1]);

        }

        printf("%lld\n", ans );

        return 0;

}