[HYSBZ - 3252] 攻略

比眉伴天荒 2021-11-02 14:56 377阅读 0赞

## 问题描述 ##

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

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

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

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

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

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

“我已经看到结局了。”

## 输入格式 ##

第一行两个正整数n,k

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

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

保证场景1为根节点

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

## 输出格式 ##

输出一个整数表示答案

## 样例输入 ##

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

## 样例输出 ##

## 解析 ##

显然，第一次一定是走树上权值最大的一条路径。在此后的\\(k-1\\)次中，每次都会走出去已经走过的路径以外最长的。 接下来的路径，并不一定是从根节点出发的，可以从已经走过的点的子节点出发，也一样可以满足条件。那么，设\\(f\[i\]\\)表示以\\(i\\)为根节点的子树上的最长路径长度，每次从堆中取出最长的一条路径后，把这条路径上每一个点的所有子节点的\\(f\[i\]\\)放入堆中。\\(f\[i\]\\)可以由动态规划处理，并在同时用前驱数组记录路径经过的点。

P.S. 代码中的堆是用左偏树实现的。

## 代码 ##

#include <iostream> #include <cstdio> #include <queue> #define int long long #define N 200002 using namespace std; int head[N],ver[N*2],nxt[N*2],val[N],l; int n,k,i,id,pre[N],f[N],pnt[N],son[N][2],fa[N],dis[N]; void insert(int x,int y) { l++; ver[l]=y; nxt[l]=head[x]; head[x]=l; } void dp(int x,int fa) { pre[x]=fa; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y!=fa){ dp(y,x); if(f[y]>f[x]) f[x]=f[y],pnt[x]=y; } } f[x]+=val[x]; } int merge(int x,int y) { if(x==0) return y; if(y==0) return x; if(f[x]<f[y]) swap(x,y); son[x][1]=merge(son[x][1],y); if(dis[son[x][0]]<dis[son[x][1]]) swap(son[x][0],son[x][1]); dis[x]=dis[son[x][1]]+1; fa[x]=fa[son[x][0]]=fa[son[x][1]]=x; return x; } int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; } void pop(int x) { f[x]=-1; fa[son[x][0]]=son[x][0]; fa[son[x][1]]=son[x][1]; fa[x]=merge(son[x][0],son[x][1]); } void insert(int x) { while(x){ pop(x); for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y!=pre[x]&&y!=pnt[x]) merge(y,find(n+1)); } x=pnt[x]; } } signed main() { cin>>n>>k; for(i=1;i<=n;i++) cin>>val[i],fa[i]=i; fa[n+1]=n+1;f[n+1]=-1; for(i=1;i<n;i++){ int u,v; cin>>u>>v; insert(u,v); insert(v,u); } dp(1,0); int ans=f[1]; insert(1); for(i=1;i<k;i++){ int root=find(n+1); ans+=f[root]; insert(root); } cout<<ans<<endl; return 0; }

转载于:https://www.cnblogs.com/LSlzf/p/11072548.html