WA 70 pts 求调
  • 板块P3408 恋爱
  • 楼主rich_xty
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/16 20:02
  • 上次更新2025/1/17 08:40:34
查看原帖
WA 70 pts 求调
1004245
rich_xty楼主2025/1/16 20:02
#include<bits/stdc++.h>
#define int long long
using namespace std;
double t,c;
int ha[500050],a[500050],need[500050],dp[5000050],n;
vector<int> g[500050];
priority_queue<int,vector<int>,greater<int> > q;
void dfs(int u,int fa){
	if(g[u].size()==1){
		dp[u]=a[u];
		return ;
	}
	for(int i=0;i<g[u].size();i++){
		if(g[u][i]==fa) continue;
		dfs(g[u][i],u);
	}
	while(!q.empty()) q.pop();
	for(int i=0;i<g[u].size();i++){
		if(g[u][i]==fa) continue;
		q.push(dp[g[u][i]]);
	}
	while(need[u]--){
		dp[u]+=q.top();
		q.pop();
	} 
	return ;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>t>>c;
	for(int i=1;i<=n;i++){
		int u;
		cin>>u>>a[i];
		g[i].push_back(u);
		g[u].push_back(i);
		ha[u]++;
	}
	for(int i=1;i<=n;i++) if(ha[i]) need[i]=ceil(a[i]*1.0/t*ha[i]);
	need[0]=ceil(c/t*ha[0]*1.0);
	dfs(0,-2);
	cout<<dp[0]<<'\n';
	return 0;
}

2025/1/16 20:02
加载中...