社区讨论
码风优良,为什么会只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 条回复,欢迎继续交流。
正在加载回复...