【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=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;
}
#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<<1];
int head[MAXN],cnt=1,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<<2];
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<<1].maxx,tree[now<<1|1].maxx);
    tree[now].maxp=Maxp(tree[now<<1],tree[now<<1|1]);
}
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)>>1;
    BuildTree(now<<1,l,mid); BuildTree(now<<1|1,mid+1,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=0;
    tree[now<<1].maxx+=tag; tree[now<<1|1].maxx+=tag;
    tree[now<<1].tag+=tag; tree[now<<1|1].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)>>1;
    if (L<=mid) Change(now<<1,L,R,val);
    if (R>mid) Change(now<<1|1,L,R,val);
    Update(now);
}
int main()
{
    N=read(); K=read();
    for (int i=1; i<=N; i++) val[i]=read();
    for (int x,y,i=1; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);
    sumV[1]=val[1]; DFS(1,0);
//    for (int i=1; i<=N; i++)
//        printf("ID=%d   [%d , %d] %d %d
",pre[i],pl[pre[i]],pr[pre[i]],val[pre[i]],sumV[pre[i]]);
    LL ans=0;
    BuildTree(1,1,N);
    for (int i=1; i<=K; i++)
        {
//            printf("NOW=%d   :  %d , %d
",i,tree[1].maxx,tree[1].maxp);
            if (tree[1].maxx>0) ans+=tree[1].maxx; else break;
            for (int x=pre[tree[1].maxp]; !visit[x]&&x; x=fa[x])
                visit[x]=1,Change(1,pl[x],pr[x],-val[x]); 
        }
    printf("%lld
",ans);
    return 0;
}

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