bzoj3252 攻略 dfs序+线段树

　　题目大意：给出一棵树，1为根节点，每个节点都有权值，每个叶子节点都是一个游戏的结局，选择k个游戏结局，使得权值总和最大，同一个节点不会被重复计算。

　　思路：这道题最关键的是要想到一个性质，就是不管怎么选，当前子树中，叶子节点最重的那一条链肯定要被选择。（可以反证，如果不选这条链，一定不是最优的），那么贪心的想一下，选取这条链之后，把这条链上的所有节点权值变成0，得到的新的树，重复以上过程k次，就得到了我们要的答案。

　　要怎么把链节点的权值变成0呢？我们建立线段树的时候，把以每个节点当成末尾节点的链当成一个元素，用这个节点的dfs序当成线段树的序号，做一个可以区间修改，查询最大值并返回下标的线段树，这样每次查询（1,n）区间最大值，就是当前最重的链，得到链后，要把这条链上每一个节点都赋值为0，并且更新其他相关链的信息。我们发现，把一个节点赋值为0，其实就是把这个节点的子树都减去此节点权值，那么就用dfs序进行区间减处理，并且把每个节点是否被删去都标记一下。如果这条链往上走的节点已经被清空了，就不需要再往上走了。这样我们会发现，每个节点最多被删除一次，每一次修改的时间复杂度是logn，所以总复杂度是nlogn，和 k 几乎无关。注意dfs序和原下标的对应。

上代码（bzoj iostream头文件居然ce了。。）

#include<cstdio>

#include<cstring>

#include<stdlib.h>

#include<cstdio>

#include<algorithm>

//#include<iostream>

#include<map>

#include<queue>

#include<vector>

#define CLR(a,b) memset(a,b,sizeof(a))

#define lson l , mid , x << 1

#define rson mid + 1 , r , x << 1 | 1

#define PI acos(-1)

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int maxn=;

struct edge{

    int to,Next;

}e[*maxn];

int n,m;

int tot,head[maxn],u,v,L[maxn],R[maxn],time,dfn[maxn],fa[maxn],ref[maxn];

ll val[maxn],dis[maxn];

bool vis[maxn];

inline void init(){

    CLR(head,-),tot=,time=;

    CLR(val,);

    dis[]=;

    CLR(vis,);

}

ll mx[maxn << ] , tag[maxn << ],mp[ maxn << ];

inline void pushup(int x)

{

    int l = x <<  , r = x <<  | ;

    if(mx[l] > mx[r]) mx[x] = mx[l] , mp[x] = mp[l];

    else mx[x] = mx[r] , mp[x] = mp[r];

}

inline void pushdown(int x)

{

    if(tag[x])

    {

        int l = x <<  , r = x <<  | ;

        mx[l] -= tag[x] , mx[r] -= tag[x];

        tag[l] += tag[x] , tag[r] += tag[x];

        tag[x] = ;

    }

}

inline void build(int l , int r , int x)

{

    if(l == r)

    {

        mx[x] = dis[l] , mp[x] = l;

        return;

    }

    int mid = (l + r) >> ;

    build(lson) , build(rson);

    pushup(x);

}

inline void update(int b , int e , ll a , int l , int r , int x)

{

    if(b <= l && r <= e)

    {

        mx[x] -= a , tag[x] += a;

        return;

    }

    pushdown(x);

    int mid = (l + r) >> ;

    if(b <= mid) update(b , e , a , lson);

    if(e > mid) update(b , e , a , rson);

    pushup(x);

}

inline void addv(int u,int v){

    e[++tot]={v,head[u]};

    head[u]=tot;

}

inline void dfs(int u,int pre){

    fa[u]=pre;

    dfn[++time]=u;

    ref[u]=time;

    L[u]=time;

    dis[time]=val[u]+dis[ref[pre]];

    for(int i=head[u];i!=-;i=e[i].Next)

    {

        int v=e[i].to;

        if(v==pre)continue;

        dfs(v,u);

    }

    R[u]=time;

}

int main(){

    int k;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        init();

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

        {

            scanf("%lld",&val[i]);

        }

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

        {

            scanf("%d%d",&u,&v);

            addv(u,v);

            addv(v,u);

        }

        dfs(,);

        build(,n,);

        ll ans=;

        int x;

        while(k--)

        {

            ans+=mx[],x=mp[];

            while(x && !vis[x])

            {

                update(L[dfn[x]],R[dfn[x]],val[dfn[x]],,n,);

                vis[x]=;

                x=ref[fa[dfn[x]]];

            }

        }

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

    }

}

Description

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

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。今天他得到了一款新游戏《XX

半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状

结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同

时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的）

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

“我已经看到结局了。”

Input

第一行两个正整数n,k

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

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

保证场景1为根节点

n<=200000，1<=场景价值<=2^31-1

Output

输出一个整数表示答案

Sample Input

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

攻略