贪心+树剖？ 从根节点开始看，如果我们选一个节点的话，肯定选一条从根节点出发往下，权值和最大的路径。 如果再选一个节点的话，候选解为：所有没被计算过的根节点的儿子，往下的权值和最大的路径、第一次选过的链的所有“分支节点”往下的权值和最大的路径。 然后第二次选择我们肯定是从这里面选一个最大的。后续贪心同理。 这一步的代码是: ```cpp 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个即可。 ```cpp #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; } ```