3252: 攻略

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 392 Solved: 157
[Submit][Status][Discuss]

Description

题目简述：树版[k取方格数]//poj3422那是个最大费用流

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。

今天他得到了一款新游戏《XX半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的）

“为什么你还没玩就知道每个场景的价值呢？”

“我已经看到结局了。”

Input

第一行两个正整数n,k

第二行n个正整数，表示每个场景的价值

以下n-1行,每行2个整数a,b，表示a场景有个选择支通向b场景（即a是b的父亲）

保证场景1为根节点

Output

输出一个整数表示答案

Sample Input

5 2
4 3 2 1 1
1 2
1 5
2 3
2 4

Sample Output

HINT

对于100%的数据，n<=200000，1<=场景价值<=2^31-1

Source

dfs序+线段树

【题解】：//主要是为了练pb_ds

每次一定是选取一个点，将它子树内权值和最大的链取走，以后就不会再选取链上的点

那么用堆维护这一过程，取最大值，删去链的所有点

复杂度都为nlogn

#include<cstdio>
#include<iostream>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
} 
typedef long long ll;
typedef pair<ll,int> pa;
typedef __gnu_pbds::priority_queue<pa > heap;
const int N=2e5+7;
struct node{
    int to,next;
}e[N];int cnt,head[N]; 
heap q;
heap::point_iterator id[N];
int n,K,v[N];
ll ans,mx[N]; 
void add(int x,int y){
    e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
}
void dp(int x){
    for(int i=head[x];i;i=e[i].next){
        dp(e[i].to);
        mx[x]=max(mx[x],mx[e[i].to]);
    }
    mx[x]+=v[x];
    id[x]=q.push(make_pair(mx[x],x));
}
void del(int x){
    q.erase(id[x]);
    for(int i=head[x];i;i=e[i].next){
        if(mx[e[i].to]==mx[x]-v[x]){
            del(e[i].to);
            break; 
        }
    }
}
int main(){
    n=read();K=read(); 
    for(int i=1;i<=n;i++) v[i]=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),add(x,y);
    dp(1); 
    for(int i=1;i<=K&&!q.empty();i++){
        pa t=q.top();
        ans+=t.first;
        del(t.second); 
    }
    printf("%lld",ans);
    return 0;
}