bzoj4726 [ POI2017 ] -- 树形DP
2018-06-17 22:45:55来源:未知 阅读 ()
显然:
1、最坏情况下最初的叛徒一定是叶子。
2、若x不是叛徒,那么x的父亲也不是叛徒。
令f[i]表示i不是叛徒的最小x,s[i]表示i的子树大小,那么答案就是所有s[i]>k的f[i]的最大值。
接下来考虑怎么求f[i]。
当i是叶子节点时,因为每个叶子节点都有可能是叛徒,所以f[i]应是1,表示只有f[i]>1时可行。
当i不是叶子节点时,枚举每个子节点j。
当j是叛徒时,f[i]>s[j]/(s[i]-1)
当j不是叛徒时,f[i]>f[j]
所以可以用min(s[j]/(s[i]-1),f[j])更新f[i]
一遍dfs就可以了。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 #define N 500010 8 vector<int>g[N]; 9 inline double Max(double x,double y){return x<y?y:x;} 10 inline double Min(double x,double y){return x<y?x:y;} 11 int i,j,k,n,m,s[N],x; 12 double f[N],Ans; 13 inline void Dfs(int x){ 14 s[x]=1; 15 for(int i=0;i<g[x].size();i++)Dfs(g[x][i]),s[x]+=s[g[x][i]]; 16 if(g[x].size()==0)f[x]=1;else 17 for(int i=0;i<g[x].size();i++)f[x]=Max(f[x],Min((double)s[g[x][i]]/(s[x]-1),f[g[x][i]])); 18 if(s[x]>k)Ans=Max(Ans,f[x]); 19 } 20 int main(){ 21 scanf("%d%d",&n,&k); 22 for(i=2;i<=n;i++)scanf("%d",&x),g[x].push_back(i); 23 Dfs(1); 24 printf("%.9lf\n",Ans); 25 return 0; 26 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:使用XUL开发跨平台桌面应用
下一篇:map/vector erase
- bzoj1864: [Zjoi2006]三色二叉树(树形DP) 2019-08-16
- 树形DP求树的直径 2019-08-16
- SICP——换零钱递归解法(树形递归) 2019-03-10
- 【树形DP】洛谷1122_最大子树和 2019-01-21
- [动态规划][树形dp]Anniversary party 2018-08-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash