# 【TopCoder SRM712】AverageVarianceSubtree

### 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 {
__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) {
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) {
}
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];
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];
}
}
}
}
}
};


## 26 thoughts to “【TopCoder SRM712】AverageVarianceSubtree”

1. Great delivery. Great arguments. Keep up the great effort.

2. 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!

3. Thank you for the good writeup. It in fact was a amusement account
By the way, how can we communicate?

4. 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!

5. 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
Chat soon!

6. 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!

7. 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
keep up the excellent jo.

8. 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.

9. It’s wonderful that you are getting thoughts from this piece of
writing as well as from our argument made at this place.

10. 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?

11. 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!

12. This is a good tip particularly to those fresh
to the blogosphere. Short but very precise info… Many thanks for sharing this one.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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!!

18. 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

19. 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?

20. 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.

21. 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?

22. Your means of describing the whole thing in this paragraph is actually good,
all can without difficulty understand it, Thanks a lot.

23. 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.

24. Looking forward to reading more. Great blog.Really looking forward to read more. Awesome.