相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3566
神犇题解：https://blog.sengxian.com/solutions/bzoj-3566
解题报告
首先根据期望的线性，我们只需要求出每个元件有电的概率，之后相加就是答案
那么怎么求每个元件有电的概率呢？我们可以无脑点分
显然在$O(n)$的时间复杂度内搞一发树形$DP$就可以了
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500009;
const int M = N << 1;
int n,head[N],nxt[M],to[M];
double up[N],down[N],cost[M],q[N],vout;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void AddEdge(int u, int v, int f) {
static int E = 1;
cost[E+1] = cost[E+2] = f / 100.0;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
void DFS1(int w, int f) {
down[w] = 1 - q[w];
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
DFS1(to[i], w);
down[w] *= down[to[i]] + (1 - down[to[i]]) * (1 - cost[i]);
}
}
}
void DFS2(int w, int f, double p) {
vout += 1 - (up[w] = down[w] * p);
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
double tmp = p * down[w] / (down[to[i]] + (1 - down[to[i]]) * (1 - cost[i]));
DFS2(to[i], w, tmp + (1 - tmp) * (1 - cost[i]));
}
}
}
int main() {
n = read();
for (int i=1,u,v;i<n;i++) {
u = read(); v = read();
AddEdge(u, v, read());
}
for (int i=1;i<=n;i++) q[i] = read() / 100.0;
DFS1(1, 1);
DFS2(1, 1, 1);
printf("%.6lf\n",vout);
return 0;
}
Quality content is the key to attract the viewers to pay a visit the site, that’s what this
site is providing.
It’s remarkable in favor of me to have a site, which is
helpful for my know-how. thanks admin
Wonderful blog! I found it while surfing around on Yahoo News.
Do you have any suggestions on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Cheers
If you desire to grow your knowledge simply keep visiting
this website and be updated with the most recent gossip posted here.
I’m not that much of a online reader to be
honest but your blogs really nice, keep it up! I’ll go ahead and bookmark your
website to come back later on. Cheers
Informative article, just what I wanted to find.
Nice blog here! Also your website loads up fast! What web
host are you using? Can I get your affiliate link to your host?
I wish my site loaded up as quickly as yours
lol
I absolutely love your website.. Excellent colors & theme.
Did you make this amazing site yourself? Please reply
back as I’m trying to create my own personal blog
and want to learn where you got this from or what the theme is called.
Thank you!
Remarkable! Its really awesome article, I have got much
clear idea about from this article.
Hello there! This is my first comment here so I just wanted to give
a quick shout out and say I genuinely enjoy reading through your
posts. Can you recommend any other blogs/websites/forums that
deal with the same topics? Thanks for your time!
Right here is the perfect blog for everyone who really wants
to find out about this topic. You know so much its almost hard to
argue with you (not that I personally would
want to…HaHa). You certainly put a new spin on a subject which has been written about for a long time.
Excellent stuff, just excellent!
naturally like your web site but you need to check the spelling on quite a
few of your posts. Several of them are rife with spelling issues and I to find it very
troublesome to tell the truth nevertheless I’ll definitely come back again.
Hello! Do you know if they make any plugins to protect
against hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?
I’m not that much of a online reader to be honest but your sites really nice, keep
it up! I’ll go ahead and bookmark your website to come back later.
Many thanks
Hi there, this weekend is good in favor of me, as this point in time i am
reading this great educational paragraph here at my home.
Highly descriptive blog, I loved that bit. Will there be a
part 2?
It’s a shame you don’t have a donate button!
I’d most certainly donate to this outstanding blog! I suppose for now i’ll settle for bookmarking and adding your RSS feed to
my Google account. I look forward to brand new updates and will talk about this website with my Facebook group.
Chat soon!
wonderful points altogether, you just gained a new reader.
What would you recommend about your put up that you made a few days in the past?
Any positive?
At this time I am going away to do my breakfast, once having my breakfast coming over again to read more
news.
Hi, I think your website might be having browser
compatibility issues. When I look at your website in Safari, it
looks fine but when opening in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up! Other then that, great blog!
plenty of fish natalielise
I think this is among the most significant info for me. And i am glad reading your article.
But wanna remark on some general things, The web site
style is great, the articles is really nice : D. Good job, cheers
I’m excited to uncover this website. I wanted to thank you for your time just for this wonderful read!!
I definitely really liked every little bit of it and i also have you saved as a favorite to
see new information on your website.
Hi to all, it’s truly a nice for me to pay a visit this web site, it contains useful Information.
I am sure this post has touched all the internet viewers, its
really really pleasant paragraph on building up new web site.
natalielise pof
Fantastic website. Plenty of helpful information here.
I’m sending it to several buddies ans also sharing in delicious.
And obviously, thanks on your sweat!
The other day, while I was at work, my sister
stole my iphone and tested to see if it can survive a 40 foot
drop, just so she can be a youtube sensation. My iPad is now
destroyed and she has 83 views. I know this is completely off topic but I had to share it with someone!
I do believe all the ideas you’ve presented to
your post. They are very convincing and will certainly work.
Still, the posts are too quick for newbies.
Could you please lengthen them a bit from subsequent time?
Thank you for the post.
It is not my first time to visit this web page, i am browsing this site dailly and obtain nice
facts from here all the time.
You really make it seem so easy with your presentation but I find this topic to be actually something that
I think I would never understand. It seems too complicated and
very broad for me. I am looking forward for your
next post, I’ll try to get the hang of it! natalielise pof
I read this piece of writing fully concerning the difference of hottest
and preceding technologies, it’s awesome article.
This is my first time pay a quick visit at here and i am in fact impressed to read all at single place.
Please let me know if you’re looking for a article writer for
your weblog. You have some really great posts and I feel I
would be a good asset. If you ever want to take some of the load off, I’d absolutely love to write some
material for your blog in exchange for a link back to
mine. Please shoot me an e-mail if interested.
Many thanks!
I for all time emailed this website post page to all my
contacts, because if like to read it afterward my contacts will too.
This website really has all the information I wanted concerning this subject and didn’t know who to ask.
I always emailed this blog post page to all my contacts,
since if like to read it afterward my links will too.
I am extremely impressed along with your writing abilities as neatly as with the layout in your
weblog. Is that this a paid theme or did you customize it your self?
Either way keep up the nice quality writing, it’s rare to
look a nice blog like this one nowadays..
No matter if some one searches for his vital thing,
therefore he/she needs to be available that in detail, therefore that thing is maintained over
here.
If some one desires expert view concerning blogging and site-building after that i recommend him/her to pay
a quick visit this website, Keep up the good job.
Hi! Do you know if they make any plugins to help with Search Engine Optimization?
I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very
good gains. If you know of any please share.
Many thanks!
Thanks in support of sharing such a pleasant thinking, piece of writing is pleasant,
thats why i have read it completely
Hello, Neat post. There is a problem with your website in web explorer, might test this?
IE nonetheless is the market leader and a huge section of other folks will pass over your magnificent
writing due to this problem.
Your style is really unique in comparison to
other people I’ve read stuff from. I appreciate you for posting when you have the opportunity,
Guess I’ll just book mark this web site.
I constantly spent my half an hour to read this weblog’s articles or reviews daily
along with a mug of coffee.
Fabulous, what a blog it is! This weblog presents valuable facts to
us, keep it up.
Pretty nice post. I just stumbled upon your blog and
wished to say that I’ve really enjoyed surfing around your blog posts.
In any case I will be subscribing to your rss feed and I hope you
write again soon!
I’ve read several good stuff here. Certainly worth bookmarking for revisiting.
I wonder how a lot attempt you place to create such a wonderful informative web site.
My brother recommended I might like this web site.
He was totally right. This put up actually made my day.
You cann’t consider simply how a lot time I had spent for this information! Thanks!
Having read this I thought it was very informative.
I appreciate you spending some time and energy to put this short article together.
I once again find myself spending way too much time both reading and commenting.
But so what, it was still worthwhile!
Good replies in return of this query with solid arguments and explaining
everything regarding that.
Aw, this was an incredibly nice post. Taking a few minutes and actual effort to create a
really good article… but what can I say… I
hesitate a whole lot and don’t seem to get anything done.
Undeniably believe that which you said. Your favorite justification seemed to be on the web the easiest thing to be aware of.
I say to you, I certainly get annoyed while people think about worries that they just do not know about.
You managed to hit the nail upon the top as well as defined
out the whole thing without having side-effects ,
people could take a signal. Will probably be back to get more.
Thanks
Wow! In the end I got a weblog from where I
be capable of truly take valuable information regarding my study
and knowledge.
Hi, i think that i saw you visited my weblog so i came to “return the favor”.I am trying to find things to improve my web site!I suppose its ok to use a few
of your ideas!!
I’ve been browsing online more than 4 hours today, yet I never found any interesting article like yours.
It is pretty worth enough for me. In my opinion, if
all site owners and bloggers made good content as you did, the web will be much more useful
than ever before.
Its like you read my mind! You appear to know so much
about this, like you wrote the book in it or something.
I think that you could do with a few pics to drive
the message home a bit, but instead of that, this is fantastic blog.
A great read. I’ll definitely be back.
I know this if off topic but I’m looking into starting my own weblog and was curious what all is required to get setup?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet savvy so I’m not 100% positive.
Any suggestions or advice would be greatly appreciated.
Thanks
obviously like your web site but you need to check the
spelling on quite a few of your posts. Several of them
are rife with spelling problems and I in finding it very
bothersome to inform the reality then again I will surely come back again.
I know this if off topic but I’m looking
into starting my own weblog and was wondering what
all is required to get set up? I’m assuming having a blog like yours would cost a pretty penny?
I’m not very web savvy so I’m not 100% sure.
Any tips or advice would be greatly appreciated.
Kudos
What i do not realize is if truth be told how you’re now not really much
more well-liked than you might be right now.
You are so intelligent. You understand thus considerably
in relation to this subject, made me in my view consider it from so many varied angles.
Its like women and men aren’t interested except it’s
one thing to do with Girl gaga! Your personal
stuffs great. Always maintain it up!
Fantastic site. Lots of useful information here.
I am sending it to some buddies ans also sharing in delicious.
And obviously, thank you for your effort!
Why visitors still make use of to read news papers when in this technological globe
everything is available on web?
I am really impressed together with your writing abilities and also with the format in your blog.
Is that this a paid subject matter or did you customize it your
self? Anyway stay up the excellent quality writing, it’s uncommon to peer a nice weblog like
this one today..
I’ll right away grasp your rss as I can’t in finding your email subscription hyperlink
or newsletter service. Do you’ve any? Please let me realize so
that I could subscribe. Thanks.
I am not sure where you are getting your info, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for fantastic information I was looking for this information for my mission.
A person necessarily help to make seriously articles I would state.
That is the very first time I frequented your web page and thus far?
I surprised with the research you made to make this actual post extraordinary.
Excellent activity!
Wonderful items from you, man. I’ve bear in mind
your stuff prior to and you’re simply too wonderful. I really like what you’ve received right here, really like
what you’re saying and the best way during which you assert it.
You make it entertaining and you continue to take
care of to keep it smart. I can’t wait to read far more from you.
This is actually a great web site.
Quality content is the important to interest the users to go to see the
site, that’s what this website is providing.
Excellent post. I was checking continuously this blog and I am impressed!
Very helpful information specifically the last part 🙂 I
care for such information a lot. I was looking for this certain info for a very long
time. Thank you and best of luck.
What’s up, just wanted to tell you, I loved this article.
It was inspiring. Keep on posting!
Hmm it appears like your site ate my first comment (it was extremely long) so I guess I’ll
just sum it up what I had written and say, I’m thoroughly enjoying
your blog. I too am an aspiring blog writer but I’m still new to
everything. Do you have any tips for rookie blog writers?
I’d certainly appreciate it.
Awesome post.
Keep on writing, great job!
Yes! Finally something about ps4 games.
I’d like to find out more? I’d want to find out more details.
Hello, I enjoy reading all of your post. I like to write a
little comment to support you.
Genuinely no matter if someone doesn’t understand then its
up to other visitors that they will assist, so here it takes place.
Great post! We will be linking to this particularly great content on our website.
Keep up the good writing.
I’m not sure where you are getting your info, but
good topic. I needs to spend some time learning more or understanding more.
Thanks for excellent information I was looking for this info for my mission.
No matter if some one searches for his vital thing, thus he/she needs to be available that in detail, therefore
that thing is maintained over here.
I’m very happy to uncover this page. I want to to thank you for your time due
to this fantastic read!! I definitely loved every part of
it and i also have you book marked to check out new things on your
web site.
Howdy would you mind letting me know which hosting company you’re working with?
I’ve loaded your blog in 3 completely different browsers and I must say this blog loads a lot faster then most.
Can you recommend a good internet hosting provider at a reasonable price?
Thanks, I appreciate it!
superb post.Never knew this, thankyou for letting me know.
all the time i used to read smaller articles or reviews that also clear their motive, and
that is also happening with this piece of writing which I
am reading at this time.
Hello it’s me, I am also visiting this web page daily,
this web page is in fact good and the users are truly
sharing fastidious thoughts.
When I initially left a comment I appear to have clicked on the -Notify me when new
comments are added- checkbox and now each time a comment is added I get four emails with the same
comment. Perhaps there is an easy method you are able to remove me from that service?
Cheers!
Hello, I enjoy reading through your article. I wanted to write
a little comment to support you.
I think this is among the most important information for me.
And i am glad reading your article. But wanna remark on few general
things, The website style is wonderful, the articles is
really great : D. Good job, cheers
It’s going to be ending of mine day, except before finish I am reading this
fantastic piece of writing to increase my experience.
Hello my family member! I wish to say that this post is amazing,
nice written and include almost all significant infos. I would like to
see more posts like this .
If some one wishes expert view regarding blogging after that i
propose him/her to pay a quick visit this website, Keep up the fastidious work.
Does your blog have a contact page? I’m having problems locating
it but, I’d like to send you an email. I’ve got some ideas for your
blog you might be interested in hearing. Either way, great blog and I look forward to seeing it develop over
time.
Please let me know if you’re looking for a writer
for your weblog. You have some really good articles and I feel I would be a good asset.
If you ever want to take some of the load off, I’d absolutely love to write some content for your blog in exchange for a link back to mine.
Please blast me an e-mail if interested. Regards!
Do you mind if I quote a few of your posts as long as I
provide credit and sources back to your webpage?
My blog site is in the very same area of interest as yours
and my visitors would certainly benefit from some of the
information you present here. Please let me know if this okay with you.
Regards!
Hello, i think that i saw you visited my website thus i came to
“return the favor”.I am attempting to find things to enhance my site!I suppose its ok to use a few of your ideas!!
Good write-up, I am regular visitor of one’s website, maintain up the excellent operate, and It is going to be a regular visitor for a lengthy time.