BZOJ 3252: 攻略

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解

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

题解

很显然每次要选择权值和最大的链。先dfs序，我们线段树维护每个点到根的权值和，然后查询和修改就行了！写的时候并不清醒、、

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=500010;
int n,q;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int v0,int n0){
        v=v0;
        nxt=n0;
    }
};
Edge e[Maxn*2];
int head[Maxn];
int nume;
long long num[Maxn];
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
    e[++nume]=Edge(u,head[v]);
    head[v]=nume;
}
int dfn[Maxn],last[Maxn];
int ind;
bool vis[Maxn];
int fa[Maxn];
int rev[Maxn];
void dfs(int x){
    vis[x]=true;
    dfn[x]=++ind;
    rev[ind]=x;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (!vis[v]){
            fa[v]=x;
            dfs(v);
        }
    }
    last[x]=ind;
}
struct Btree{
    int left,right;
    long long max;
    int ind;
    long long tag;
};
Btree tree[Maxn*4];
inline void update(int x){
    if (tree[x].left==tree[x].right) return;
    tree[x].max=max(tree[x*2].max,tree[x*2+1].max);
    if (tree[x].max==tree[x*2].max) tree[x].ind=tree[x*2].ind;
    if (tree[x].max==tree[x*2+1].max) tree[x].ind=tree[x*2+1].ind;
}
inline void clean(int x){
    if (tree[x].left==tree[x].right) return;
    if (tree[x].tag){
        tree[x*2].tag+=tree[x].tag;
        tree[x*2].max+=tree[x].tag;
        tree[x*2+1].tag+=tree[x].tag;
        tree[x*2+1].max+=tree[x].tag;
        tree[x].tag=0;
    }
}
void build(int x,int left,int right){
    tree[x].left=left;
    tree[x].right=right;
    tree[x].max=0;
    tree[x].tag=0;
    if (left==right){
        tree[x].ind=left;
    }else{
        int mid=(left+right)/2;
        build(x*2,left,mid);
        build(x*2+1,mid+1,right);
        update(x);
    }
}
void change(int x,int left,int right,long long val){
    clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        tree[x].tag+=val;
        tree[x].max+=val;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (left<=mid) change(x*2,left,right,val);
        if (mid<right) change(x*2+1,left,right,val);
        update(x);
    }
}
struct Ret{
    int ind;
    long long max;
    Ret(){}
    Ret(int i0,long long m0){
        ind=i0;
        max=m0;
    }
};
Ret query(int x,int left,int right){
    clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        return Ret(tree[x].ind,tree[x].max);
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        Ret ret=Ret(0,0),tmp;
        if (left<=mid) {
            tmp=query(x*2,left,right);
            if (tmp.max>ret.max) ret=tmp;
        }
        if (mid<right) {
            tmp=query(x*2+1,left,right);
            if (tmp.max>ret.max) ret=tmp;
        }
        return ret;
    }
}
long long Ans;
int main(){
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++) scanf("%lld",&num[i]);
    for (int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addEdge(x,y);
    }
    fa[1]=0;
    dfs(1);
    build(1,1,n);
    for (int i=1;i<=n;i++)
        change(1,dfn[i],last[i],num[i]);
    /*for (int i=1;i<=n;i++){
        printf("%d->%d\n",rev[i],i);
    }*/
    memset(vis,false,sizeof(vis));
    for (int i=1;i<=q;i++){
        /*for (int i=1;i<=n;i++)
            printf("%d ",query(1,i,i).max);
        printf("\n");*/
        Ret ans=query(1,1,n);
        Ans+=ans.max;
        int ind=rev[ans.ind];
        //cout<<ans.ind<<"->"<<ans.max<<endl;
        do{
            //ind=rev[ind];
            //printf("Del %d\n",ind);
            vis[ind]=true;
            change(1,dfn[ind],last[ind],-num[ind]);
            ind=fa[ind];
        }while(vis[ind]==false && ind!=0);
    }
    printf("%lld\n",Ans);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=500010;

int n,q;

struct Edge{

int v,nxt;

Edge(){}

Edge(int v0,int n0){

v=v0;

nxt=n0;

}

};

Edge e[Maxn*2];

int head[Maxn];

int nume;

long long num[Maxn];

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

e[++nume]=Edge(u,head[v]);

head[v]=nume;

}

int dfn[Maxn],last[Maxn];

int ind;

bool vis[Maxn];

int fa[Maxn];

int rev[Maxn];

void dfs(int x){

vis[x]=true;

dfn[x]=++ind;

rev[ind]=x;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (!vis[v]){

fa[v]=x;

dfs(v);

}

last[x]=ind;

}

struct Btree{

int left,right;

long long max;

int ind;

long long tag;

};

Btree tree[Maxn*4];

inline void update(int x){

if (tree[x].left==tree[x].right) return;

tree[x].max=max(tree[x*2].max,tree[x*2+1].max);

if (tree[x].max==tree[x*2].max) tree[x].ind=tree[x*2].ind;

if (tree[x].max==tree[x*2+1].max) tree[x].ind=tree[x*2+1].ind;

}

inline void clean(int x){

if (tree[x].left==tree[x].right) return;

if (tree[x].tag){

tree[x*2].tag+=tree[x].tag;

tree[x*2].max+=tree[x].tag;

tree[x*2+1].tag+=tree[x].tag;

tree[x*2+1].max+=tree[x].tag;

tree[x].tag=0;

}

void build(int x,int left,int right){

tree[x].left=left;

tree[x].right=right;

tree[x].max=0;

tree[x].tag=0;

if (left==right){

tree[x].ind=left;

}else{

int mid=(left+right)/2;

build(x*2,left,mid);

build(x*2+1,mid+1,right);

update(x);

}

void change(int x,int left,int right,long long val){

clean(x);

if (left<=tree[x].left && tree[x].right<=right){

tree[x].tag+=val;

tree[x].max+=val;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (left<=mid) change(x*2,left,right,val);

if (mid<right) change(x*2+1,left,right,val);

update(x);

}

struct Ret{

int ind;

long long max;

Ret(){}

Ret(int i0,long long m0){

ind=i0;

max=m0;

}

};

Ret query(int x,int left,int right){

clean(x);

if (left<=tree[x].left && tree[x].right<=right){

return Ret(tree[x].ind,tree[x].max);

}else{

int mid=(tree[x].left+tree[x].right)/2;

Ret ret=Ret(0,0),tmp;

if (left<=mid) {

tmp=query(x*2,left,right);

if (tmp.max>ret.max) ret=tmp;

}

if (mid<right) {

tmp=query(x*2+1,left,right);

if (tmp.max>ret.max) ret=tmp;

}

return ret;

}

long long Ans;

int main(){

scanf("%d%d",&n,&q);

for (int i=1;i<=n;i++) scanf("%lld",&num[i]);

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

int x,y;

scanf("%d%d",&x,&y);

addEdge(x,y);

}

fa[1]=0;

dfs(1);

build(1,1,n);

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

change(1,dfn[i],last[i],num[i]);

/*for (int i=1;i<=n;i++){

printf("%d->%d\n",rev[i],i);

}*/

memset(vis,false,sizeof(vis));

for (int i=1;i<=q;i++){

/*for (int i=1;i<=n;i++)

printf("%d ",query(1,i,i).max);

printf("\n");*/

Ret ans=query(1,1,n);

Ans+=ans.max;

int ind=rev[ans.ind];

//cout<<ans.ind<<"->"<<ans.max<<endl;

do{

//ind=rev[ind];

//printf("Del %d\n",ind);

vis[ind]=true;

change(1,dfn[ind],last[ind],-num[ind]);

ind=fa[ind];

}while(vis[ind]==false && ind!=0);

}

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

return 0;

}

WNJXYKの博客

喂你脚下有坑

BZOJ 3252: 攻略

Description

Input

Output

Sample Input

Sample Output

HINT

题解

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

2022年 8月
一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

BZOJ 3252: 攻略

Description

Input

Output

Sample Input

Sample Output

HINT

题解

扫一扫支付

评论 放弃治疗

评论放弃治疗