问题描述
题目简述: 树版 [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
样例输出
10
解析
显然, 第一次一定是走树上权值最大的一条路径. 在此后的 \(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;
- }
[HYSBZ - 3252] 攻略
来源: http://www.bubuko.com/infodetail-3101223.html