【TopCoder SRM712】AverageVarianceSubtree

相关链接

题目传送门: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];
						}
					}
				}
			}
		}
};

26 thoughts to “【TopCoder SRM712】AverageVarianceSubtree”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Leave a Reply to http://tinyurl.com/ Cancel reply

Your email address will not be published. Required fields are marked *