【题解】ABC259F Select Edges

Sol

考虑 dp。
记 \(dp_{u,0/1}\) 表示 \(u\) 点是否向上连边的最大值。
转移的话相当于是找若干个 \(dp_{v,1}+w(u,v)\) 进行转移。
其中 \(w(u,v)\) 表示 \((u,v)\) 这条边的权值。
那么每次开个 vector 把 \(dp_{v,1}+w(u,v)\) 存下来然后排个序，找最大的 \(d_u\) 个节点即可。
时间复杂度 \(O(n \log n)\)。

Code

//LYC_music yyds!
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
#define int long long
using namespace std;
inline char gc()
{
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read()
{
	int pos=1,num=0;
	char ch=getchar();
	while (!isdigit(ch))
	{
		if (ch=='-') pos=-1;
		ch=getchar();
	}
	while (isdigit(ch))
	{
		num=num*10+(int)(ch-'0');
		ch=getchar();
	}
	return pos*num;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
void writesp(int x)
{
	write(x);
	putchar(' ');
}
void writeln(int x)
{
	write(x);
	putchar('\n');
}
const int N=3e5+10;
vector<pair<int,int> > G[N];
int n,a[N],dp[N][2];
void dfs(int u,int fa)
{
	int s=0; vector<int> g;
	for (auto [v,w]:G[u])
	{
		if (v==fa) continue;
		dfs(v,u); s+=dp[v][0];
		g.emplace_back(dp[v][1]-dp[v][0]+w);
	}
	sort(g.begin(),g.end(),greater<int>());
	for (int i=0;i<min((int)g.size(),a[u]-1);i++)
		s+=max(0ll,g[i]);
	dp[u][0]=s+(g.size()>a[u]-1?max(0ll,g[a[u]-1]):0);
	if (!a[u]) dp[u][1]=-0x3f3f3f3f3f3f3f3f;
	else dp[u][1]=s;
}
signed main()
{
	n=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	for (int i=1;i<n;i++)
	{
		int u=read(),v=read(),w=read();
		G[u].emplace_back(v,w); G[v].emplace_back(u,w);
	}
	dfs(1,0);
	writeln(max(dp[1][0],dp[1][1]));
}