rt
TLE+WA,除了#subtask2就没有一个点是AC的
但是我觉得思路应该没问题啊,题解也是类似的思路
求大佬帮忙看看,蟹蟹了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5e5+10,MAXM=1e6+20;
struct Edge{
int u,v;
}edge[MAXM];
int first[MAXN],next[MAXM],tot,size[MAXN],Limit[MAXN];
int ans=-1;
int a[MAXN],n,m;
long long f[MAXN][2],c[MAXN];
void addedge(int u,int v){
tot++;
edge[tot].u=u;edge[tot].v=v;
next[tot]=first[u];
first[u]=tot;
size[u]++;
}
void dfs(int u,int fa){
f[u][0]=f[u][1]=-1e9;
int cnt=0;
long long sum=0;
for(int j=first[u];j;j=next[j]){
int v=edge[j].v;
if(v==fa)continue;
dfs(v,u);
c[++cnt]=f[v][1]-f[v][0];
sum+=f[v][0];
}
if(!cnt){
//叶子
f[u][0]=min(a[u],a[fa]);
if(a[u]>a[fa]){
f[u][1]=a[u];
}else{
f[u][1]=-1e9;
}
return;
}
sort(c+1,c+1+cnt,greater<int>());
for(int j=first[u];j;j=next[j]){
int v=edge[j].v;
if(v==fa)continue;
//推导u - fa的边符合fa能忍受的情况
//1. 满足fa也满足u,选min(u,fa)
//2. 满足fa但大于u,选fa(如果在fa>u)
// 然后u就少选一个
//1.
long long now=sum+min(a[u],a[fa]);
for(int i=1;i<=cnt&&i<=Limit[u];i++){
if(c[i]>=0){
now+=c[i];
}else break;
}
f[u][0]=max(f[u][0],now);
//2.
if(a[fa]>a[u]){
now=sum+a[fa];
for(int i=1;i<=cnt&&i<Limit[u];i++){
if(c[i]>=0){
now+=c[i];
}else break;
}
f[u][0]=max(f[u][0],now);
}
//1.要么u和fa都不能忍受这条边,那就Limit-1个+m
//2.要么fa不能忍受但是u可以,那就Limit个+u(当a[u]>a[fa]时)
now=sum+m;
for(int i=1;i<=cnt&&i<Limit[u];i++){
if(c[i]>=0){
now+=c[i];
}else break;
}
f[u][1]=max(f[u][1],now);
//2.
if(a[u] > a[fa]){
now=sum+a[u];
for(int i=1;i<=cnt&&i<=Limit[u];i++){
if(c[i]>=0){
now+=c[i];
}else break;
}
f[u][1]=max(f[u][1],now);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
addedge(u,v);
addedge(v,u);
}
for(int i=1;i<=n;i++){
//size[i]-size[i]/2-1个
Limit[i]=size[i]-(size[i]>>1)-1;
}
for(int j=first[1];j;j=next[j]){
int v=edge[j].v;
dfs(v,1);
}
//最后以1为根节点来一次贪心(选Limit个)
int cnt=0;
long long sum=0,now=0;
for(int j=first[1];j;j=next[j]){
int v=edge[j].v;
c[++cnt]=f[v][1]-f[v][0];
sum+=f[v][0];
}
sort(c+1,c+1+cnt,greater<int>());
now=sum;
for(int i=1;i<=cnt&&i<=Limit[1];i++){
if(c[i]>=0){
now+=c[i];
}else break;
}
cout<<now<<endl;
return 0;
}