1 题目大意

给定一棵树，每个结点两个权值 a,b 。

令一个合法的方案为一个点 u 和一个点集 v，满足以下要求

• ∀x∈v ，满足 x 是 u 子树中的结点（包括 u 本身）
• ∑bvi≤m

令一个方案的贡献为 au⋅|b|

求最大贡献

注意到一个点的最优方案显然是其子树中尽可能选择小的。

发现问题可以合并。如果完成了一个结点所有直接儿子的处理，那么将儿子所选的结点合并到一起然后再选择即可。

实际上可以考虑维护可并堆和堆中值的和。每次合并完后弹出堆顶直到合法为止。

注意到每个结点最多被插入一次，删除一次，故复杂度 O(nlog⁡(n))

3 Code

#include <cstdio>

#include <algorithm>

const int N = 1e5 + 1e4;

typedef long long ll;

// Leftist Tree
struct HeapNode {
    int val, dist, cnt;
    ll sum;
    HeapNode *son[2];
    HeapNode( int _val, int _dist, int _cnt, ll _sum) { 
        val = _val; dist = _dist; cnt = _cnt; sum = _sum;
        son[0] = son[1] = 0;
    }

    inline void push_up() {
        cnt = ( son[0]? son[0] -> cnt: 0 ) +
            ( son[1]? son[1] -> cnt: 0 ) + 
            1;
        sum = ( son[0]? son[0] -> sum: 0 ) +
            ( son[1]? son[1] -> sum: 0 ) + 
            val;
        dist = son[1]? ( son[1] -> dist + 1 ): 1;
    }
};

int get_dist( HeapNode *cur ) { return cur? cur -> dist: -1; }

HeapNode* merge( HeapNode *from, HeapNode *to ) {
    if( !from || !to ) 
        return from? from: to;
    if( to -> val > from -> val )
        std::swap( from, to );
    from -> son[1] = merge( from -> son[1], to );
    if( get_dist( from -> son[0] ) < get_dist( from -> son[1] ) ) 
        std::swap( from -> son[0], from -> son[1] );
    from -> push_up();
    return from;
}

// Graph
struct Edge {
    int to, next;
} e[N];
int ehead[N], ecnt;
inline void add_edge( int cur, int to ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[cur];
    ehead[cur] = ecnt;
}

int n, m;
ll ans;
int price[N], leader[N];

HeapNode* dfs( int cur ) {
    HeapNode *rt = new HeapNode( price[cur], 0, 1, price[cur] );
    for( int i = ehead[cur]; i; i = e[i].next ) {
        rt = merge( rt, dfs( e[i].to ) );
    }
    while( rt -> sum > m ) {
        HeapNode *tmp = rt;
        rt = merge( rt -> son[0], rt -> son[1] );
        delete(tmp);
    }
    ans = std::max( ans, 1LL * leader[cur] * ( rt -> cnt ) );
    return rt;
}

void dfs_free( HeapNode *cur ) {
    if( cur -> son[0] ) 
        dfs_free( cur -> son[0] );
    if( cur -> son[1] ) 
        dfs_free( cur -> son[1] );
    delete cur;
}

int main() {
#ifdef woshiluo
    freopen( "luogu.1552.in", "r", stdin );
    freopen( "luogu.1552.out", "w", stdout );
#endif
    int rt = 1;
    scanf( "%d%d", &n, &m );
    for( int i = 1; i <= n; i ++ ) {
        int b, c, l;
        scanf( "%d%d%d", &b, &c, &l );
        price[i] = c; leader[i] = l;
        if( b == 0 ) 
            rt = i;
        else 
            add_edge( b, i );
    }

    HeapNode *tmp = dfs(rt);
    dfs_free(tmp);

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

class

OI

发表评论 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注