【BZOJ-3252】攻略 DFS序 + 线段树 + 贪心

3252: 攻略

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 339 Solved: 130
[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

Source

dfs序+线段树

Solution

比较好想的一道题

首先，K次攻略，使总价值最大，显然每次攻略当前最大即可

我们定义一个节点的Val为根到这个节点的∑val

那么我们用线段树维护一下这个东西，每次取最大。

考虑统计一次答案之后，这个点的价值就不存在了，那么我们只需要把这个点到根的路径上的所有点的val在它的子树中减去即可

每个点只减一次就可以了....

所以时间复杂度还是$O(nlogn)$的

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

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

    return x*f;

}

#define MAXN 200010

#define LL long long

int N,K;

bool visit[MAXN];

LL sumV[MAXN],val[MAXN];

struct EdgeNode{int next,to;}edge[MAXN<<];

int head[MAXN],cnt=,fa[MAXN];

void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}

void InsertEdge(int u,int v) {fa[v]=u; AddEdge(u,v); AddEdge(v,u);}

int pl[MAXN],pr[MAXN],dfn,pre[MAXN];

void DFS(int now,int last)

{

    pl[now]=++dfn; pre[dfn]=now;

    for (int i=head[now]; i; i=edge[i].next)

        if (edge[i].to!=last)

            sumV[edge[i].to]=sumV[now]+val[edge[i].to],DFS(edge[i].to,now);

    pr[now]=dfn;

}

struct SegmentTreeNode{int l,r,maxp; LL maxx,tag;}tree[MAXN<<];

int Maxp(SegmentTreeNode ls,SegmentTreeNode rs) {return ls.maxx>rs.maxx? ls.maxp:rs.maxp;}

void Update(int now)

{

    tree[now].maxx=max(tree[now<<].maxx,tree[now<<|].maxx);

    tree[now].maxp=Maxp(tree[now<<],tree[now<<|]);

}

void BuildTree(int now,int l,int r)

{

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

    if (l==r) {tree[now].maxx=sumV[pre[l]]; tree[now].maxp=l; return;}

    int mid=(l+r)>>;

    BuildTree(now<<,l,mid); BuildTree(now<<|,mid+,r);

    Update(now);

}

void PushDown(int now)

{

    if (tree[now].l==tree[now].r || !tree[now].tag) return;

    LL tag=tree[now].tag; tree[now].tag=;

    tree[now<<].maxx+=tag; tree[now<<|].maxx+=tag;

    tree[now<<].tag+=tag; tree[now<<|].tag+=tag;

}

void Change(int now,int L,int R,int val)

{

    PushDown(now);

    int l=tree[now].l,r=tree[now].r;

    if (L<=l && R>=r) {tree[now].maxx+=val; tree[now].tag+=val; return;}

    int mid=(l+r)>>;

    if (L<=mid) Change(now<<,L,R,val);

    if (R>mid) Change(now<<|,L,R,val);

    Update(now);

}

int main()

{

    N=read(); K=read();

    for (int i=; i<=N; i++) val[i]=read();

    for (int x,y,i=; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);

    sumV[]=val[]; DFS(,);

//    for (int i=1; i<=N; i++)

//        printf("ID=%d   [%d , %d] %d %d\n",pre[i],pl[pre[i]],pr[pre[i]],val[pre[i]],sumV[pre[i]]);

    LL ans=;

    BuildTree(,,N);

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

        {

//            printf("NOW=%d   :  %d , %d\n",i,tree[1].maxx,tree[1].maxp);

            if (tree[].maxx>) ans+=tree[].maxx; else break;

            for (int x=pre[tree[].maxp]; !visit[x]&&x; x=fa[x])

                visit[x]=,Change(,pl[x],pr[x],-val[x]);

        }

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

    return ;

}

第一次明白攻略组的意思....大概是看刀剑的时候吧/....

秒客网