题目链接:http://codeforces.com/contest/767/problem/C


问能否将一棵带点权的书分成点权$3$块,求任意方案。

其实考虑一棵以$x$为根的子树权值为${\frac{1}{3}\sum val[i]}$之后它就一定要作为单独的一块了,那么DFS一遍即可。


 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 1000010
#define llg long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,ans[maxn],tot,val[maxn],size[maxn],sum,dad[maxn],root;
vector<llg>a[maxn]; void dfs(llg x,llg fa)
{
if (tot==) return ;
llg w=a[x].size(),v;
size[x]=val[x];
for (llg i=;i<w;i++)
{
if (tot==) return ;
v=a[x][i];
if (v==fa) continue;
if (tot==) return ;
dfs(v,x);
if (tot==) return ;
size[x]+=size[v];
}
if (size[x]==sum) {ans[++tot]=x; size[x]=;}
if (tot==) return ;
} void init()
{
cin>>n;
for (llg i=;i<=n;i++)
{
scanf("%I64d%I64d",&dad[i],&val[i]);
if (dad[i]==) root=i;
a[dad[i]].push_back(i);
sum+=val[i];
}
} int main()
{
// yyj("C");
init();
if (sum%!=) {cout<<-; return ;}
sum/=;
dfs(root,);
sort(ans+,ans+tot+);
for (llg i=;i<=n;i++)
if (ans[i]==root)
{
cout<<-;
return ;
}
if (tot>=) {for (llg i=;i<=tot;i++) cout<<ans[i]<<" "; }else cout<<-;
return ;
}

最新文章

  1. Less:优雅的写CSS代码
  2. APUE学习--第三版apue编译
  3. Windows api实现桌面任务栏隐藏\显示
  4. Nancy+BUI+SQLite自动更新服务端和客户端保护更新程序
  5. Servlet与JSP的区别
  6. floyd算法 青云的机房组网方案(简单)
  7. 使用Adreno Profiler分析android游戏
  8. ToolStripStatusLabel设置时间自动更新
  9. Linux UDEV和为MySQL InnoDB共享表空间配置裸设备
  10. maven学习2,安装插件
  11. 献身说法---修复bug时的一些小技巧
  12. 认识 Linux 文件权限
  13. BBS论坛(十七)
  14. UML 教程
  15. Linux bash基础特性二
  16. [20190130]删除tab$记录的恢复2.txt
  17. 解决 linux 下面解压缩 中文文件名乱码问题的方法 unzip -O CP936
  18. vue 自学项目笔记
  19. Nginx 访问日志配置
  20. 如何查看yum 安装的软件路径

热门文章

  1. 75.Java异常处理机制-自定义异常
  2. SQL表分区之二
  3. 简单的图像显著性区域特征提取方法-----opencv实现LC,AC,FT
  4. Spring基于的注解自动装配和依赖注入(***)
  5. sqlalchemy学习笔记
  6. Elasticstarch 相关
  7. 框架frame
  8. 在C#中使用OpenCV(使用OpenCVSharp)
  9. webpack对于引入的模块无法智能代码提示
  10. 【python001-IDLE】