树形DP re求助
查看原帖
树形DP re求助
590571
_weishiqi66_楼主2023/11/24 13:42

本地测过udebug的数据,答案是对的。测评结果是RE,各位大佬帮忙看看

#include<bits/stdc++.h>
#define qwq 	cout<<"over"<<endl;
using namespace std;
const int N=1e6;
int n,T;
vector<int> son[N];
int dp(int u){
	if(son[u].empty()) return 1;
	priority_queue<int,vector<int>,greater<int> > q;
	int k=son[u].size();
	for(int i=0;i<k;i++){
		q.push(dp(son[u][i]));
	}
	int c=(k*T-1)/100+1;
	int ans=0;
	for(int i=0;i<c;i++){
		ans+=q.top();
		q.pop();
	}
	while(!q.empty()) q.pop();
	return ans;
}
int main(){
//freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	while(1){
		scanf("%d%d",&n,&T);
		if(n==0) break;
		for(int i=0;i<=N;i++){
			vector<int>().swap(son[i]);
		}
		for(int i=1;i<=n;i++){
			int c; scanf("%d",&c);
			son[c].push_back(i);
		}
		printf("%d\n",dp(0));
	}
	return 0;
}
2023/11/24 13:42
加载中...