贪心+树剖？

从根节点开始看，如果我们选一个节点的话，肯定选一条从根节点出发往下，权值和最大的路径。

如果再选一个节点的话，候选解为：所有没被计算过的根节点的儿子，往下的权值和最大的路径、第一次选过的链的所有“分支节点”往下的权值和最大的路径。

然后第二次选择我们肯定是从这里面选一个最大的。后续贪心同理。

这一步的代码是:

const int N = 5e6+10;
vector<vector<int>> g;
int a[N],son[N],val[N];
int p[N];
int n,m;
void dfs1(int u,int fa){
	son[u] = -1;
	for(auto v:g[u]){
		if(v == fa) continue;
		dfs1(v,u);
		if(son[u] == -1|| val[v] > val[son[u]]) son[u] = v,val[u] = val[v];
	}
	val[u] += a[u];
}
ll ans = 0;

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	g = vector<vector<int>>(n+1);
	for(int i=2;i<=n;i++) cin>>p[i],g[p[i]].push_back(i);
	dfs1(1,-1);

	priority_queue<pii> pq;

	auto dfs2 = [&](auto &&dfs2,int u)->void{
		for(auto v:g[u]){
			if(v!=son[u]){
				pq.push({val[v],v});
			}
		}
		if(son[u]!=-1){
			dfs2(dfs2,son[u]);
		}
	};

	pq.push({val[1],1});
	while(pq.size() && m ){
		auto [v,u] = pq.top();
		pq.pop(); m--;
		ans += v;

		dfs2(dfs2,u);

	}
	cout<<ans<<endl;
}

但是常数太大T了。 考虑一下可以不用优先队列，直接先处理出解空间中的路径，根据路径和sort一下取最大的m个即可。

#include<bits/stdc++.h>
#define endl '\n'


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int N = 5e6+10;
//vector<vector<int>> g;
int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {  // ch 不是数字时
    if (ch == '-') w = -1;        // 判断是否为负
    ch = getchar();               // 继续读入
  }
  while (ch >= '0' && ch <= '9') {  // ch 是数字时
    x = x * 10 + (ch - '0');  // 将新读入的数字「加」在 x 的后面
    // x 是 int 类型，char 类型的 ch 和 '0' 会被自动转为其对应的
    // ASCII 码，相当于将 ch 转化为对应数字
    // 此处也可以使用 (x<<3)+(x<<1) 的写法来代替 x*10
    ch = getchar();  // 继续读入
  }
  return x * w;  // 数字 * 正负号 = 实际数值
}
int h[N],e[N],ne[N],idx;
void add(int a,int b){
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

int a[N],son[N],val[N];
int p[N];
int n,m;
void dfs1(int u,int fa){
	son[u] = -1;
	for(int i = h[u];i!=-1;i = ne[i]){
		int v  = e[i];
		if(v == fa) continue;
		dfs1(v,u);
		if(son[u] == -1|| val[v] > val[son[u]]) son[u] = v,val[u] = val[v];
	}
	val[u] += a[u];
}
ll ans = 0;
vector<int> path;
void dfs2(int u,int fa,bool flag){
	if(flag) path.emplace_back(val[u]);
	for(int i = h[u];i!=-1;i=ne[i]){
		int v = e[i];
		if(v == son[u]){
			dfs2(v,u,false);
		}else{
			dfs2(v,u,true);
		}
	}
}
void solve(){
	n = read(),m = read();
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++) a[i] = read();
	//g = vector<vector<int>>(n+1);
	for(int i=2;i<=n;i++) p[i] = read(),add(p[i],i);
	dfs1(1,-1);
	dfs2(1,-1,true);
	sort(path.begin(),path.end(),greater<int>());
	m = min(m,(int)path.size());
	for(int i = 0;i<m;i++){
		ans += path[i];
	}
	cout<<ans<<endl;

}

int main(){		
    ifstream test_file("0in.txt");
    if (test_file) {
        freopen("0in.txt", "r", stdin);
        freopen("0output.txt", "w", stdout);
    }
	std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
	int T = 1;
#ifdef MULTI_TEST
	cin>>T;
#endif
	while(T--){
		solve();
	}
	return 0;
}