相关链接
题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14568&rd=16881
题目大意
给定一棵$n(n \le 50)$个结点的树,每个点上有一个点权$a_i(a_i \le 10^9)$
让你从中随意选出一个连通子图,询问这个连通子图中的每一个点的权值组成的序列的方差的期望是多少
小数输出,最终误差不得大于$\frac{1}{10^9}$
解题报告
将方差的式子化一化,发现我们大概要维护$E(\sum{a_i^2})$和$E((\sum{a_i})^2)$
第一个可以直接维护
第二个那一坨,我们还是使用期望的线性将其拆开,分别维护即可
最后再做一个树$DP$,总的复杂度大概在$O(n^3)$
Code
long double
最后一个点被卡精度了,只能用__float128
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 59; const int M = N << 1; class AverageVarianceSubtree { int n,E,head[N],nxt[M],to[M]; __float128 ans,tot,val[N],s1[N][N],s2[N][N],s3[N][N],cnt[N][N]; public: double average(vector<int> p, vector<int> weight) { E = 1; ans = tot = 0; memset(head,0,sizeof(head)); memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); memset(s3,0,sizeof(s3)); memset(cnt,0,sizeof(cnt)); n = weight.size(); for (int i=1;i<=n;i++) val[i] = weight[i - 1]; for (int i=0;i<n-1;i++) AddEdge(i + 2, p[i] + 1); DFS(1, 1); for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { ans += (s2[i][j] - s3[i][j] / j) / j; tot += cnt[i][j]; } } return ans / tot; } private: inline void AddEdge(int u, int v) { to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } void DFS(int w, int f) { cnt[w][0] = cnt[w][1] = 1; s1[w][1] = val[w]; s2[w][1] = s3[w][1] = val[w] * val[w]; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { DFS(to[i], w); for (int t=n;t;t--) { for (int a=1,b;b=t-a,a<t;a++) { s3[w][t] += s3[w][a] * cnt[to[i]][b] + s3[to[i]][b] * cnt[w][a] + 2 * s1[w][a] * s1[to[i]][b]; s1[w][t] += s1[w][a] * cnt[to[i]][b] + s1[to[i]][b] * cnt[w][a]; s2[w][t] += s2[w][a] * cnt[to[i]][b] + s2[to[i]][b] * cnt[w][a]; cnt[w][t] += cnt[w][a] * cnt[to[i]][b]; } } } } } };
Great post. I’m facing a few of these issues as well..
Great delivery. Great arguments. Keep up the great effort.
I’m really enjoying the design and layout of your site.
It’s a very easy on the eyes which makes it much more pleasant for me to
come here and visit more often. Did you hire out a designer to create your theme?
Exceptional work!
Thank you for the good writeup. It in fact was a amusement account
it. Look advanced to more added agreeable from you!
By the way, how can we communicate?
What i do not realize is in reality how you’re now not really a lot more smartly-appreciated than you might
be right now. You are very intelligent. You know therefore considerably relating to this matter, made me individually consider it from so many various angles.
Its like women and men aren’t interested until it’s one thing to do with
Woman gaga! Your own stuffs outstanding. At all times handle it up!
It’s a pity you don’t have a donate button!
I’d without a doubt donate to this brilliant blog!
I suppose for now i’ll settle for bookmarking and adding
your RSS feed to my Google account. I look forward
to fresh updates and will share this site with my Facebook group.
Chat soon!
Greetings, There’s no doubt that your site may be having internet browser
compatibility issues. When I look at your website in Safari, it looks fine however, if opening in Internet Explorer, it has some overlapping issues.
I just wanted to give you a quick heads up! Aside from that, excellent blog!
Howdy I am so grateful I found your site, I really found
you by accident, while I was looking on Bing for something else, Nonetheless I am here now and would just like to say kudos for a marvelous post
and a all round thrilling blog (I also love the theme/design),
I don’t have time to browse it all at the moment but I have saved it and also
included your RSS feeds, so when I have time I will
be back to read a great deal more, Please do
keep up the excellent jo.
Do you have a spam issue on this site; I also am a blogger, and
I was wondering your situation; many of us have developed some nice procedures and
we are looking to swap techniques with others, why not
shoot me an e-mail if interested.
It’s wonderful that you are getting thoughts from this piece of
writing as well as from our argument made at this place.
I am really loving the theme/design of your blog.
Do you ever run into any internet browser compatibility issues?
A number of my blog visitors have complained about my blog not operating correctly in Explorer but looks great
in Firefox. Do you have any recommendations to help fix this issue?
Hi there! This is my 1st comment here so I just wanted
to give a quick shout out and tell you I genuinely enjoy reading through your blog
posts. Can you suggest any other blogs/websites/forums that cover the
same subjects? Thanks a ton!
This is a good tip particularly to those fresh
to the blogosphere. Short but very precise info… Many thanks for sharing this one.
A must read article!
I’ve been exploring for a little bit for any high-quality articles or blog posts on this kind of space . Exploring in Yahoo I eventually stumbled upon this web site. Reading this info So i am happy to exhibit that I have an incredibly excellent uncanny feeling I discovered exactly what I needed. I such a lot indubitably will make sure to don’t omit this web site and give it a look on a relentless basis.
With havin so much content do you ever run into any problems of plagorism or copyright infringement?
My website has a lot of unique content I’ve either
authored myself or outsourced but it appears a lot of
it is popping it up all over the internet without my agreement.
Do you know any techniques to help protect against content from being stolen? I’d certainly appreciate it.
Attractive component of content. I just stumbled upon your site and in accession capital to
claim that I acquire in fact loved account your weblog posts.
Anyway I will be subscribing for your feeds or even I success you
access persistently quickly.
Does your blog have a contact page? I’m having a tough time locating it but, I’d like to shoot you an email.
I’ve got some creative ideas for your blog you might be
interested in hearing. Either way, great blog and I look forward to seeing
it expand over time.
Hi, i think that i noticed you visited my weblog so i got here to return the favor?.I am attempting to in finding issues to enhance my web site!I assume its ok to make
use of some of your ideas!!
Hey! This is kind of off topic but I need some advice from an established blog.
Is it very difficult to set up your own blog? I’m not very techincal but I can figure things out pretty quick.
I’m thinking about making my own but I’m not sure where to begin. Do you
have any points or suggestions? Thanks
I’m curious to find out what blog system you happen to be utilizing?
I’m experiencing some minor security issues
with my latest website and I would like to find something more safe.
Do you have any solutions?
I got this site from my pal who told me regarding this web page and now this time I
am visiting this web site and reading very informative articles or reviews at this place.
excellent points altogether, you simply gained a emblem new reader.
What would you recommend in regards to your publish that you just made a few days in the past?
Any sure?
Your means of describing the whole thing in this paragraph is actually good,
all can without difficulty understand it, Thanks a lot.
We’re a group of volunteers and opening a new scheme in our community. Your website offered us with valuable info to work on. You’ve done an impressive job and our whole community will be thankful to you.
This is one awesome post.Much thanks again. Awesome.
Looking forward to reading more. Great blog.Really looking forward to read more. Awesome.