社区讨论

码风优良,为什么会只A了一个点呢?(其他全WA)

P3915树的分解参与者 2已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lqyl5som
此快照首次捕获于
2024/01/04 10:26
2 年前
此快照最后确认于
2024/01/04 16:47
2 年前
查看原帖
我还手搓了几个数据,都没啥问题的来着,这个题不让下载数据可还行
CPP
#include <bits/stdc++.h>
using namespace std;
int T,n,k,ans;
vector <int> mp[100010];
int ok[100010],okk;
int dfs (int ni)
{
	if (okk==-1) return 0;
//	cout<<ni<<"!"<<endl;
	int s=0;
	for (vector<int>::iterator it=mp[ni].begin();it!=mp[ni].end();it++) {
		if (!ok[*it]) {
			ok[*it]=1;
			s+=dfs(*it);
		}
	}
	s++;
//	cout<<ni<<" "<<s<<" "<<ans<<endl; 
	if (s==k) {
		ans++;
		return 0;
	}
	if (s>k) {
		okk=-1;
		return 0;
	}
	return s;
}
int main()
{
	scanf("%d",&T);
	while (T--) {
		okk=0; ans=0;
		scanf("%d%d",&n,&k);
		if (n%k) {
			cout<<"NO"<<endl;
			continue;
		}
		for (int i=1;i<=n;i++) mp[i].clear();
		for (int i=0;i<=n;i++) ok[i]=0;
		for (int i=1;i<n;i++) {
			int a,b;
			scanf("%d%d",&a,&b);
			mp[a].push_back(b); mp[b].push_back(a);
		}
//		for (int i=1;i<=n;i++) {
//			for (vector<int>::iterator it=mp[i].begin();it!=mp[i].end();it++)
//				cout<<*it<<" ";
//			cout<<endl;
//		}
		mp[0].push_back(1);
		dfs(0);
		if (okk==-1) cout<<"NO"<<endl;
		else if (ans==n/k) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
	return 0;
}
/*
5
6 3
1 2
2 3
3 4
4 5
2 6

6 3
1 2
2 3
3 4
4 5
3 6

6 3
1 2
2 3
3 4
4 5
1 6

*/

回复

7 条回复,欢迎继续交流。

正在加载回复...