P10641 BZOJ3252 攻略

题目链接

简要题意

给定一个有 \(n\) 个结点的树，树有点权且点权为正整数。现选取 \(k\) 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。

主要算法

贪心，树链剖分，（线段树合并）

思路

1. 一个显然的贪心，每次选一点点权和最大的链，再讲这条链清为0。正确性我不会证，但比较容易感性理解。
2. 直接模拟的复杂度是 \(O(nk)\) 的显然不可接受。所以考虑如何优化，看到树看到链，就会想到树链剖分。
3. 树链剖分后这些链是没有重复的点的，所以与题目同一场景多次观看不会得到重复价值一样，但我要保证贪心选的链一定是我划分的链，所以我们按当前点到叶子的路径上的点权和值重链剖分。
4. 剖分完，排序即可

#include <bits/stdc++.h>
using namespace std;
const int mod=(1<<30),N=2e5+10;
int n,k,in[N],nxt[N],go[N],hd[N],son[N],w[N],tot,cnt,rt;
long long ans,jz[N],siz[N];
void add(int u,int v)
{
	nxt[++tot]=hd[u];go[tot]=v;hd[u]=tot;
	in[v]++;
	return;
}
void dfs1(int u,int f)
{
	for(int i=hd[u];i;i=nxt[i])
	{
		int v=go[i];
		dfs1(v,u);
		siz[u]=max(siz[u],siz[v]);
		if(siz[v]>siz[son[u]])son[u]=v;
	}
	siz[u]+=w[u];
}
void dfs2(int u)
{
	if(son[u])dfs2(son[u]);
	for(int i=hd[u];i;i=nxt[i])
	{
		int v=go[i];
		if(v==son[u])continue;
		jz[++cnt]=siz[v];
		dfs2(v);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++)if(!in[i]) rt=i;
	dfs1(rt,0);
	dfs2(rt);
	jz[++cnt]=siz[rt];
	sort(jz+1,jz+cnt+1);
	for(int i=cnt;i>=cnt-k+1;i--)ans+=jz[i];//long long
	cout<<ans;
	return 0;
}