【贪心】 BZOJ 3252:攻略

3252: 攻略

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 261 Solved: 90
[Submit][Status][Discuss]

Description

题目简述：树版[k取方格数]

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略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

　　很容易知道贪心策略:每次选价值最高的叶子节点

　　但是貌似很难搞的样子

　　朴素算法应该是n^2的样子。。

　　O（n）显然不太好搞。。

　　所以大约优化完后是O（nlgn）左右的复杂度。。

　　有两种logn的方法

　　1.黄学长的堆。。自行百度。。我只能说代码完全看不懂。。

　　2.DFS序+线段树

　　DFS处理出一个点管辖的所有点的DFS序。

　　然后线段树添加，每次删除。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<vector>

 #define maxn 200001

 using namespace std;

 vector<int>graph[maxn];

 int rev[maxn],in[maxn],father[maxn],dfn[maxn],last[maxn],tot=;

 long long a[maxn];

 bool vis[maxn];

 struct tr{

     int l,r,ps;

     long long num,tag;

 }tree[maxn*];

 long long read()

 {

     long long x=;char ch=getchar();

     while(ch<''||ch>'')ch=getchar();

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return x;

 }

 void DFS(int poi)

 {

     dfn[poi]=++tot;

     rev[tot]=poi;

     for(int i=graph[poi].size()-;i>=;i--)

     {

         int u=graph[poi][i];

         DFS(u);

     }

     last[poi]=tot;

 }

 void psh(int poi)

 {

     if(tree[poi].tag&&tree[poi].l!=tree[poi].r)

     {

     tree[poi<<].tag+=tree[poi].tag;

     tree[(poi<<)|].tag+=tree[poi].tag;

     tree[poi<<].num+=tree[poi].tag;

     tree[(poi<<)|].num+=tree[poi].tag;

     tree[poi].tag=;

     }

 }

 void update(int num,int l,int r,long long d)

 {

     psh(num);

     if(tree[num].l==l&&tree[num].r==r)

     {

         tree[num].num+=d;

         tree[num].tag+=d;

         return;

     }

     int mid=(tree[num].l+tree[num].r)>>;

     if(mid>=r)update(num<<,l,r,d);

     else if(l>mid)update((num<<)|,l,r,d);

     else update(num<<,l,mid,d),update((num<<)|,mid+,r,d);

     if(tree[num].l==tree[num].r)return;

     if(tree[num<<].num>tree[(num<<)|].num){tree[num].num=tree[num<<].num,tree[num].ps=tree[num<<].ps;}

     if(tree[(num<<)|].num>=tree[num<<].num){tree[num].num=tree[(num<<)|].num,tree[num].ps=tree[(num<<)|].ps;}

 }

 void build(int num,int l,int r)

 {

     if(l==r)

     {

         tree[num].l=tree[num].r=l;

         tree[num].ps=l;

         return;

     }

     int mid=(l+r)>>;

     build(num<<,l,mid);

     build((num<<)|,mid+,r);

     tree[num].l=l,tree[num].r=r;

     tree[num].ps=tree[(num<<)|].ps;

 }

 int main()

 {

     long long ans=;

     int n,k;

     n=read(),k=read();

     for(int i=;i<=n;i++)a[i]=read();

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

     {

         int u,v;

     u=read();v=read();

     graph[u].push_back(v);

     father[v]=u;

     }

     father[]=;

     DFS();

     build(,,n);

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

         update(,dfn[i],last[i],a[i]);

     while(k--)

     {

     psh();

     ans+=tree[].num;

     int u=rev[tree[].ps];

     while(u&&!vis[u])

     {

         vis[u]=;

         update(,dfn[u],last[u],-a[u]);

         u=father[u];

     }

     }

     printf("%lld",ans);

     return ;

 }

　　(死于太久没打tag。。)

秒客网