题解 洛谷 P3915 【树的分解】
2022/9/10 6:23:11
本文主要是介绍题解 洛谷 P3915 【树的分解】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1## P3915 树的分解
题目描述
给出\(N\)个点的树和K,问能否把树划分成\(\frac{N}{K}\)个连通块,且每个连通块的点数都是\(K\)。
解题思路
分析样例:
「\(sample1\)」
可被划分为\(1\).\(2\)、\(3\).\(4\)两个大小为\(2\)的连通块。
「\(sample2\)」
无法被划分为大小为\(2\)的连通块
我们可以整理出以下思路:
[1] 若总点数\(N\)无法被\(K\)整除,则无法被恰好分成\(\frac{N}{K}\)个连通块。
[2] 考虑统计每个子树的大小,在当前子树大小恰好为\(K\)时将其赋值为\(0\)(相当于删除)并将这个连通块计入答案中。
注意事项
多组测试数据时要将变量清零。
#include<bits/stdc++.h> #define re register #define il inline #define MAXN 100005 #define rep(i,a,b) for(re int i = a;i <= b;++ i) #define Rep(i,a,b) for(re int i = a;i < b;++ i) #define drep(i,a,b) for(re int i = a;i >= b;-- i) #define Drep(i,a,b) for(re int i = a;i > b;-- i) #define star(i,x) for(re int i = head[x];i;i = e[i].nxt) #define fin(a) freopen(#a".in","r",stdin) #define fout(a) freopen(#a".out","w",stdout) using namespace std; il int read(){ int x = 0; char ch = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)){ x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } return x; } il void write(int x){ if(x > 9) write(x / 10); write(x % 10 + '0'); } struct edge{ int nxt,to; }e[MAXN << 1]; int head[MAXN << 1],cnt = 0,ans = 0; int t,n,k; int siz[MAXN]; il void add(int u,int v){ e[++ cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt; } il void dfs(int x,int fa){ siz[x] = 1; star(i,x){ int v = e[i].to; if(v != fa){ dfs(v,x); siz[x] += siz[v]; } } if(siz[x] == k){ siz[x] = 0; ans ++; } } int main(){ #ifndef ONLINE_JUDGE fin(3915); fout(3915); #endif t = read(); while(t --){ n = read(),k = read(); ans = 0,cnt = 0; memset(head,0,sizeof(head)); memset(siz,0,sizeof(siz)); memset(e,0,sizeof(e)); Rep(i,1,n){ int u = read(),v = read(); add(u,v); add(v,u); } if(n % k != 0){ printf("NO\n"); continue; } dfs(1,0); if(ans == n / k) printf("YES\n"); else printf("NO\n"); } return 0; }
这篇关于题解 洛谷 P3915 【树的分解】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行