bzoj4726 [ POI2017 ] -- 树形DP

2018-06-17 22:45:55来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

显然:

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 }
bzoj4726

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:使用XUL开发跨平台桌面应用

下一篇:map/vector erase