综合电商网站建设需求文档,南宁广告网页设计招聘信息,什么是网络营销促销?,安徽网站建设公司思维#xff0c;简单树$dp$。 首先计算出每一个子树包含多少个节点#xff0c;记为$f[i]$。然后就可以从$root$开始推出所有节点的期望了。 现在已知$fa$节点的答案为$ans[fa]$#xff0c;假设要计算$fa$的一个儿子$v$的期望#xff0c;那么$ans[v]ans[fa]1.0(f[fa]-f[v]-1…思维简单树$dp$。 首先计算出每一个子树包含多少个节点记为$f[i]$。然后就可以从$root$开始推出所有节点的期望了。 现在已知$fa$节点的答案为$ans[fa]$假设要计算$fa$的一个儿子$v$的期望那么$ans[v]ans[fa]1.0(f[fa]-f[v]-1)/2.0$。 我画了一下样例然后猜测了一下发现是对的...... #pragma comment(linker, /STACK:1024000000,1024000000)
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includevector
#includemap
#includeset
#includequeue
#includestack
#includeiostream
using namespace std;
typedef long long LL;
const double piacos(-1.0),eps1e-8;
void File()
{freopen(D:\\in.txt,r,stdin);freopen(D:\\out.txt,w,stdout);
}
template class T
inline void read(T x)
{char c getchar(); x 0;while(!isdigit(c)) c getchar();while(isdigit(c)) { x x * 10 c - 0; c getchar(); }
}const int maxn100010;
double ans[maxn];
vectorintg[maxn];
int n,f[maxn];void dfs(int x)
{f[x]0;for(int i0;ig[x].size();i){dfs(g[x][i]);f[x]f[x]f[g[x][i]];}f[x];
}void get(int x)
{for(int i0;ig[x].size();i){ans[g[x][i]]ans[x]1.01.0*(f[x]-f[g[x][i]]-1)/2.0;get(g[x][i]);}
}int main()
{scanf(%d,n);for(int i2;in;i){int fa; scanf(%d,fa);g[fa].push_back(i);}dfs(1); ans[1]1.0; get(1); for(int i1;in;i) printf(%.6lf ,ans[i]);printf(\n);return 0;
} 转载于:https://www.cnblogs.com/zufezzt/p/5798395.html
