首页 > 代码库 > 【BZOJ-3252】攻略 DFS序 + 线段树 + 贪心

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

2024-08-12 11:12:35   221人阅读

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

10

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 longint 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\n",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\n",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\n",ans);    return 0;}

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

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


联系
我们