QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394691#6745. Delete the TreeLo#RE 0ms0kbC++141.3kb2024-04-20 17:50:012024-04-20 17:50:03

Judging History

你现在查看的是最新测评结果

  • [2024-04-20 17:50:03]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-20 17:50:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=505;
vector<int> e[N],w[N];
int n,x,y,del[N],dp[N][2];
int dfs(int u,int fa)
{
	dp[u][1]=1;
	for (auto v:e[u])
	{
		if (v==fa) continue;
		dfs(v,u);
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		dp[u][1]+=dp[v][0];
	}
	if (e[u].size()>2) dp[u][1]=0; 
}
vector<int> b;
void solve(int u,int fa,int flg)
{
	if (flg)
	{
		del[u]=1;
		b.push_back(u);
		for (auto x:e[u])
			for (auto y:e[u])
			{
				if (x==y) continue;
				w[x].push_back(y);
//				cout<<u<<":("<<x<<","<<y<<")\n";
			}
		for (auto v:e[u])
			if (v!=fa) solve(v,u,0);
		return;
	}
	for (auto v:e[u])
	{
		if (v==fa) continue;
		if (dp[v][1]>dp[v][0]) solve(v,u,1);
		else
		{
			w[u].push_back(v);
			w[v].push_back(u);
			solve(v,u,0);
		}
	}
}
int main()
{
	cin>>n;
	for (int i=1;i<n;++i)
	{
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	vector<vector<int>> ans;
	while (n)
	{
		int t=1;
		while (del[t]) t++;
		dfs(t,0);
		if (dp[t][1]>dp[t][0]) solve(t,0,1);
		else solve(t,0,0);
		memset(dp,0,sizeof(dp));
		int m=0;
		for (int i=1;i<=n;++i)
		{
			e[i]=w[i];
			w[i].clear();
			m+=(!del[i]);
		}
		n=m;
		ans.push_back(b);
		b.clear();
	}
	cout<<ans.size()<<"\n";
	for (auto v:ans)
	{
		cout<<v.size();
		for (auto t:v) cout<<" "<<t;
		cout<<"\n";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5
1 2
1 3
1 4
4 5

output:


result: