相关链接
题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
解题报告
这题告诉我们,这类题可以高斯消元做
裸做是$O(n^3)$的,非常不科学
这题我们发掘性质,如果从叶子开始一层一层往上消,高斯消元那一块可以做到$O(n)$
然后再算上逆元的话,总的时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 200009; const int MOD = 1000000007; int n, head[N], nxt[M], to[M], cost[M]; int a[N], b[N], fa[N], d[N]; inline int read() { char c=getchar(); int f=1,ret=0; 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 c) { static int E = 1; d[u]++; d[v]++; cost[E + 1] = cost[E + 2] = c; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline int REV(int x) { int ret = 1, t = MOD - 2; for (; t; x = (LL)x * x % MOD, t >>= 1) { if (t & 1) { ret = (LL)ret * x % MOD; } } return ret; } void solve(int w, int f) { if (d[w] > 1) { a[w] = -1; for (int i = head[w]; i; i = nxt[i]) { b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD; if (to[i] != f) { solve(to[i], w); } } if (w != f) { b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD; a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD; } } } int main() { #ifdef DBG freopen("11input.in", "r", stdin); #endif n = read(); for (int i = 1; i < n; ++i) { int u = read(), v = read(); AddEdge(u + 1, v + 1, read()); } solve(1, 1); int ans = (LL)b[1] * REV(MOD - a[1]) % MOD; ans = (ans + MOD) % MOD; cout<<ans<<endl; return 0; }
楼下是疯子。哈哈
You should take part in a contest for one of the finest sites
on the web. I most certainly will recommend this web site!
First of all I would like to say wonderful blog!
I had a quick question that I’d like to ask if you don’t mind.
I was curious to know how you center yourself and clear your thoughts prior to writing.
I have had a hard time clearing my mind in getting my thoughts out.
I truly do enjoy writing however it just seems like the first 10 to 15
minutes tend to be wasted just trying to figure out how to begin. Any suggestions or tips?
Appreciate it!
When I originally commented I clicked the “Notify me when new comments are added” checkbox
and now each time a comment is added I get four e-mails with the same comment.
Is there any way you can remove me from that service? Cheers!
Wow! In the end I got a blog from where I be able to genuinely take helpful data
concerning my study and knowledge.
I really like what you guys are usually up too.
This kind of clever work and coverage! Keep up the superb works guys I’ve
included you guys to my blogroll.
Thanks very interesting blog!
Hello there! This blog post couldn’t be written any better!
Going through this article reminds me of my previous roommate!
He continually kept preaching about this.
I most certainly will forward this article to him.
Pretty sure he’ll have a very good read. I appreciate you
for sharing!
Hey There. I found your blog using msn.
This is an extremely well written article. I’ll be sure to bookmark it and return to
read more of your useful info. Thanks for the post. I’ll certainly
return.
What’s up i am kavin, its my first occasion to commenting anyplace, when i read
this piece of writing i thought i could also create comment
due to this brilliant post.
When I initially commented I seem to have clicked on the -Notify me when new comments
are added- checkbox and now each time a comment is added I receive four emails
with the exact same comment. There has to be a way you are
able to remove me from that service? Cheers!
You need to take part in a contest for one of the greatest
blogs on the internet. I most certainly will highly recommend this website!
I relish, lead to I found just what I used to
be looking for. You have ended my 4 day lengthy hunt!
God Bless you man. Have a nice day. Bye
I’m impressed, I have to admit. Seldom do I encounter a blog that’s both equally educative and amusing, and let me tell you, you have hit the nail on the head.
The problem is something which too few men and women are
speaking intelligently about. Now i’m very happy I
stumbled across this in my search for something
regarding this.
Undeniably believe that that you stated. Your favourite reason appeared to be on the web the
simplest thing to take note of. I say to you, I certainly get irked whilst other folks consider concerns that they just
do not understand about. You controlled to hit the nail
upon the top and also outlined out the entire thing with
no need side effect , folks could take a signal. Will likely be
back to get more. Thank you
Hey are using WordPress for your site platform? I’m new to the blog world but I’m trying to get started and set up my own.
Do you need any coding expertise to make your own blog? Any help would be greatly appreciated!
natalielise plenty of fish
I am really impressed with your writing skills as well as with the layout
on your blog. Is this a paid theme or did you modify it
yourself? Either way keep up the excellent quality writing, it’s
rare to see a nice blog like this one today.
Howdy! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any recommendations?
Nice weblog here! Additionally your website loads up very fast!
What web host are you the usage of? Can I get your associate link for
your host? I want my web site loaded up as quickly as yours lol
Appreciating the dedication you put into your site and in depth information you present.
It’s awesome to come across a blog every once in a while that isn’t the same out of date rehashed information. Wonderful
read! I’ve bookmarked your site and I’m adding your RSS feeds to my
Google account. natalielise plenty of fish
If you desire to get a good deal from this paragraph then you have to apply these strategies to your won web site.
Excellent blog right here! Also your website quite a
bit up very fast! What web host are you the use of?
Can I get your affiliate link to your host? I wish
my website loaded up as quickly as yours lol
Hello to all, the contents present at this web page are
actually awesome for people knowledge, well, keep up the
good work fellows.
Hmm is anyone else having problems with the images on this blog loading?
I’m trying to determine if its a problem on my
end or if it’s the blog. Any responses would be greatly appreciated.
plenty of fish natalielise
An intriguing discussion is definitely worth comment. There’s no doubt that that you
ought to publish more on this topic, it might not be a taboo subject but usually folks don’t discuss these subjects.
To the next! Kind regards!! natalielise plenty of fish
you are really a just right webmaster. The web site loading velocity is incredible.
It sort of feels that you are doing any unique trick.
Moreover, The contents are masterpiece. you’ve done a fantastic task in this
matter!
Howdy! Do you use Twitter? I’d like to follow you
if that would be ok. I’m undoubtedly enjoying your blog and look forward
to new posts.
I’m not sure exactly why but this web site is loading very slow for me.
Is anyone else having this problem or is it a issue on my end?
I’ll check back later and see if the problem still exists.
I really like what you guys tend to be up too.
Such clever work and exposure! Keep up the awesome works guys I’ve included you
guys to my blogroll.
We absolutely love your blog and find the majority of your post’s to be precisely what I’m looking for.
can you offer guest writers to write content available for you?
I wouldn’t mind publishing a post or elaborating on a lot of
the subjects you write concerning here. Again, awesome
weblog!
It is appropriate time to make some plans for the future and it is
time to be happy. I’ve read this post and if I could I wish to
suggest you few interesting things or suggestions. Perhaps
you could write next articles referring to this article. I desire to read more things about it!
Does your site have a contact page? I’m having trouble locating
it but, I’d like to send you an email. I’ve got some suggestions for your blog you
might be interested in hearing. Either way, great
website and I look forward to seeing it improve over time.
A person essentially assist to make significantly posts I’d state.
That is the very first time I frequented your web page and up to now?
I amazed with the analysis you made to create this actual publish amazing.
Wonderful process!
Thanks in support of sharing such a fastidious thought, post is pleasant, thats why i have read it entirely
Hi there Dear, are you in fact visiting this site regularly, if so afterward you will definitely get pleasant know-how.
When someone writes an piece of writing he/she retains the
idea of a user in his/her brain that how a user can understand it.
Thus that’s why this piece of writing is perfect. Thanks!
If you are going for finest contents like I do, only go to
see this site all the time since it presents quality contents,
thanks
Hi there, i read your blog occasionally and i own a
similar one and i was just wondering if you get a lot
of spam comments? If so how do you prevent it, any plugin or anything you can suggest?
I get so much lately it’s driving me insane so any assistance is very
much appreciated.
I value the article post.Really looking forward to read more. Will read on…
Say, you got a nice blog article.Thanks Again.
Really enjoyed this article.Really thank you! Cool.
Very good post.Really looking forward to read more. Much obliged.
Really enjoyed this blog article.
Im obliged for the blog.Really looking forward to read more. Great.
Im obliged for the blog post.Thanks Again. Keep writing.
Hey, thanks for the blog.Really looking forward to read more. Really Great.
I appreciate you sharing this blog article.Thanks Again. Great.
Thanks a lot for the article post.Really looking forward to read more. Keep writing.
Really enjoyed this blog.Really looking forward to read more. Awesome.
Muchos Gracias for your article.Thanks Again. Keep writing.
Major thanks for the blog.Thanks Again. Want more.
Major thankies for the post.Much thanks again.
Really appreciate you sharing this blog.Really thank you! Will read on…
I value the article.Really looking forward to read more. Want more.
Hey, thanks for the blog post.Much thanks again. Keep writing.
Hey! I just wanted to ask if you ever have any issues with
hackers? My last blog (wordpress) was hacked and
I ended up losing several weeks of hard work due
to no data backup. Do you have any methods to protect against hackers?
Great, thanks for sharing this article.Really looking forward to read more. Will read on…
I really enjoy the post.Really thank you! Keep writing.
A big thank you for your blog article. Want more.
Say, you got a nice blog post.Really thank you! Keep writing.
Say, you got a nice article.Really thank you!
A big thank you for your blog.Thanks Again. Really Great.
Great, thanks for sharing this article.Really looking forward to read more. Really Cool.
It’s an amazing paragraph in favor of all the web visitors; they will take advantage from it
I am sure.
Thanks-a-mundo for the blog article.Really thank you! Really Great.
Awesome article.Really looking forward to read more. Want more.
Im obliged for the article. Want more.
I appreciate you sharing this blog.Really looking forward to read more. Great.
Wow, great blog article.Really thank you! Really Great.
Thanks for the post.Much thanks again. Will read on…
Thanks a lot for the post.Really thank you! Want more.
Major thanks for the blog.Really thank you! Much obliged.
Thanks for the blog article.Thanks Again.
Major thankies for the post.Much thanks again. Much obliged.
Thanks for sharing, this is a fantastic post.Really looking forward to read more. Will read on…
Im thankful for the post.Really thank you! Will read on…
Very informative article post.Really thank you! Much obliged.
Thanks for sharing, this is a fantastic blog post.Much thanks again. Awesome.
Really informative blog.Much thanks again. Cool.
Thanks for the article post.Much thanks again. Want more.
wow, awesome blog post.Much thanks again. Want more.
I really like and appreciate your article post.Much thanks again. Really Cool.
I cannot thank you enough for the blog post.Much thanks again. Keep writing.
Very good article post.Much thanks again. Much obliged.
Thanks for sharing, this is a fantastic post.Much thanks again. Much obliged.
Very informative blog. Much obliged.
Thanks again for the blog article.Thanks Again. Cool.
I truly appreciate this post.Thanks Again. Cool.
Enjoyed every bit of your article.Much thanks again. Really Cool.
Great, thanks for sharing this blog post. Awesome.
Thanks for sharing, this is a fantastic blog.Thanks Again. Keep writing.
Thank you for your blog article.Really thank you! Really Cool.
Fantastic post.Really thank you!
This is one awesome blog post. Fantastic.
Hey, thanks for the blog post. Great.
Enjoyed every bit of your article post.Really looking forward to read more. Great.
Really appreciate you sharing this blog.Really thank you! Want more.
Enjoyed every bit of your blog.Much thanks again. Cool.
Great, thanks for sharing this post.Much thanks again. Want more.
Looking forward to reading more. Great blog article.Much thanks again. Keep writing.
I appreciate you sharing this blog article.Much thanks again. Awesome.
Appreciate you sharing, great blog post.Really thank you! Fantastic.
A big thank you for your article post.Really thank you! Want more.
Fantastic article post.Really thank you! Much obliged.
I cannot thank you enough for the article.Really thank you! Awesome.
Great, thanks for sharing this blog post.Really looking forward to read more. Cool.
Hey, thanks for the blog post. Really Great.
Im obliged for the article post. Really Cool.
A round of applause for your blog post.Thanks Again. Cool.
Very good blog post.Really looking forward to read more. Great.
Exceptional post however , I was wanting to know if you could
write a litte more on this subject? I’d be very thankful if you
could elaborate a little bit further. Bless you!
Hey, thanks for the blog post.Much thanks again. Much obliged.
Very good article.Much thanks again. Great.
Thanks so much for the blog post.Really looking forward to read more. Much obliged.
Major thankies for the article post.Really looking forward to read more. Awesome.
Wow, great blog.Really looking forward to read more. Great.
Hey, thanks for the blog post.Really looking forward to read more. Awesome.
Enjoyed every bit of your article post. Keep writing.
Very neat blog.Thanks Again. Much obliged.
This is one awesome post. Cool.
Major thankies for the blog.Really thank you! Want more.
In fact no matter if someone doesn’t know
afterward its up to other users that they
will help, so here it happens.
Im obliged for the blog post.Really looking forward to read more. Really Cool.
Fantastic article post.Thanks Again. Will read on…
Really informative post.Much thanks again. Keep writing.
I value the article post.Thanks Again. Will read on…
I appreciate you sharing this blog post. Fantastic.
Looking forward to reading more. Great blog article. Will read on…
Very neat blog post.Much thanks again. Great.
Thanks so much for the blog article.Really looking forward to read more. Will read on…
Thanks so much for the blog article.Really looking forward to read more. Cool.
Major thanks for the article.Really looking forward to read more. Will read on…
Thanks in favor of sharing such a pleasant idea, paragraph
is pleasant, thats why i have read it entirely
I cannot thank you enough for the blog.Really looking forward to read more. Cool.
Im thankful for the blog. Really Great.
Hello it’s me, I am also visiting this website on a regular basis, this
web site is actually pleasant and the visitors are really
sharing nice thoughts.
Say, you got a nice post.Thanks Again. Cool.
I really like and appreciate your article.Much thanks again. Really Cool.
Thanks for the article.Much thanks again.
Thanks-a-mundo for the blog post.Really thank you! Will read on…
Very good post.Really thank you! Awesome.
I cannot thank you enough for the article.Really looking forward to read more. Awesome.
Thanks-a-mundo for the post.Really thank you! Keep writing.
Wow, great blog. Really Great.
Thanks again for the post.Thanks Again. Great.
Im grateful for the article. Really Cool.
A big thank you for your post.Thanks Again. Keep writing.
Thanks a lot for the post.Really thank you! Great.
Thanks for sharing, this is a fantastic article post.Much thanks again.
Thank you ever so for you blog post.Really thank you! Keep writing.
Enjoyed every bit of your article post.Really thank you!
Thank you for your article.Much thanks again. Really Great.
Looking forward to reading more. Great article. Want more.
Hey, thanks for the article.
Awesome blog article.Thanks Again. Really Cool.
Major thankies for the blog post.Really thank you! Really Great.
Appreciate you sharing, great blog post. Really Cool.
You’re so awesome! I don’t think I’ve truly read through anything like this before.
So wonderful to discover someone with a few original thoughts on this subject matter.
Seriously.. thank you for starting this up. This website is something that is required on the web,
someone with a bit of originality!
wow, awesome post.Thanks Again. Really Cool.
Really appreciate you sharing this article post.Really thank you! Really Great.
I cannot thank you enough for the blog article.Much thanks again. Really Great.
Thanks a lot for the blog.Thanks Again. Awesome.
Great article.Thanks Again. Really Great.
Very good article post.Thanks Again. Awesome.
Thank you ever so for you blog post.Really looking forward to read more. Great.
Im obliged for the blog post.Really looking forward to read more. Will read on…
I really like and appreciate your article.Much thanks again. Will read on…
Thanks so much for the blog.Really thank you!
Enjoyed every bit of your blog.Really thank you! Much obliged.
Thanks again for the blog article.
Thank you ever so for you blog article. Much obliged.
This is one awesome post.
I am so grateful for your article post.Much thanks again. Cool.
Just wanted to say thanks for posting this!
I appreciate you sharing this article post. Keep writing.
Hey there! I could have sworn I’ve been to this website before but after browsing through some of the post I realized it’s new to me.
Anyhow, I’m definitely happy I found it and I’ll be book-marking and checking
back often!
I cannot thank you enough for the post.Much thanks again. Keep writing.
I simply could not leave your web site before suggesting that I actually loved the usual information an individual provide on your guests? Is gonna be again ceaselessly to inspect new posts.
Good article. I absolutely love this site.
Keep writing!
I am so grateful for your blog article. Fantastic.
I am so grateful for your blog article.Really thank you! Fantastic.
Wow, great article post.Really looking forward to read more. Much obliged.
You actually make it appear really easy together with your presentation however
I in finding this topic to be actually one thing that I think I’d by no means understand.
It kind of feels too complex and very huge for me. I’m having a look ahead for your subsequent put up, I’ll try to get the hang of it!
Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.
You clearly know what youre talking about, why waste your intelligence on just posting videos to your site when you could be giving us something informative to read?
Generally I do not read post on blogs, however I wish to say that this write-up very forced me to take a
look at and do so! Your writing taste has been surprised me.
Thanks, very great post.
Useful information. Lucky me I discovered your website unintentionally, and I am shocked why this coincidence didn’t
took place in advance! I bookmarked it.
It’s amazing to go to see this site and reading the views
of all colleagues regarding this post, while I am also eager of getting know-how.
Howdy! I just want to give you a big thumbs up
for your great info you’ve got here on this post. I’ll be coming back to your web site for more soon.
If some one wishes to be updated with most recent technologies then he must be go to
see this site and be up to date everyday.
Magnificent beat ! I would like to apprentice while you amend your
website, how could i subscribe for a weblog website? The account aided
me a appropriate deal. I have been tiny bit acquainted of this your broadcast offered vivid transparent concept
Hey there superb website! Does running a blog like this require a massive amount work?
I’ve absolutely no expertise in programming however I had
been hoping to start my own blog soon. Anyway, if you have any suggestions or
tips for new blog owners please share. I know this is off topic however I just needed to ask.
Many thanks!
Pretty great post. I simply stumbled upon your weblog and wished to mention that I have truly loved
surfing around your weblog posts. After all I will be subscribing for your feed and I am
hoping you write again soon!
Hi there friends, nice piece of writing and good arguments commented here, I am truly enjoying
by these.
I pay a visit everyday a few web sites and websites to read content, however this
weblog provides quality based articles.
Hi, i think that i saw you visited my blog so i
got here to return the favor?.I am trying to to find issues to enhance my web
site!I guess its ok to use a few of your ideas!!
Normally I do not learn post on blogs, but I would like
to say that this write-up very compelled me to take a look at and do it!
Your writing taste has been amazed me. Thank you, very great
post.
I like the valuable info you provide in your articles.
I will bookmark your weblog and check again here regularly.
I’m quite certain I’ll learn a lot of new stuff right here!
Best of luck for the next!
great put up, very informative. I ponder why the other
specialists of this sector don’t notice this. You should proceed your
writing. I am sure, you’ve a huge readers’ base already!
Hi would you mind letting me know which hosting company you’re utilizing? I’ve loaded your blog in 3 completely different browsers and I must say this blog loads a lot quicker then most. Can you recommend a good hosting provider at a fair price? Cheers, I appreciate it!
Thanks on your marvelous posting! I genuinely enjoyed reading it,
you may be a great author. I will remember to bookmark your
blog and definitely will come back in the foreseeable
future. I want to encourage you continue your great posts, have a nice
weekend!
This post is genuinely a good one it helps new internet viewers,
who are wishing for blogging.
It’s very effortless to find out any topic on web as compared to books,
as I found this post at this web site.
It’s a pity you don’t have a donate button! I’d definitely donate to this superb
blog! I guess for now i’ll settle for book-marking and adding
your RSS feed to my Google account. I look forward to brand new updates and will
share this site with my Facebook group. Talk soon!
I loved as much as you will receive carried out right here.
The sketch is tasteful, your authored material
stylish. nonetheless, you command get got an nervousness over that you wish be delivering the following.
unwell unquestionably come further formerly again as exactly the
same nearly very often inside case you shield this hike.
I know this website provides quality dependent articles and
other material, is there any other site which presents such information in quality?
Please let me know if you’re looking for a author for your site.
You have some really great posts and I believe I would be a good asset.
If you ever want to take some of the load off, I’d really like to write some content for your blog in exchange for a link back to mine.
Please shoot me an email if interested. Regards!
fantastic points altogether, you simply received
a brand new reader. What may you recommend about your post that you made some days ago?
Any certain?
Pretty nice post. I just stumbled upon your blog and wanted to say that I have truly enjoyed browsing your blog
posts. In any case I will be subscribing to your
feed and I hope you write again very soon!
Hi to all, how is everything, I think every one is getting more from this site, and
your views are nice in support of new visitors.
Hi outstanding blog! Does running a blog like this require a massive amount
work? I’ve no understanding of computer programming but I was hoping to start my own blog soon. Anyhow, should you have any ideas or techniques for new blog
owners please share. I understand this is off topic however I simply
wanted to ask. Thank you!
I am actually thankful to the owner of this web site who has shared this
impressive post at at this time.
Hello, i think that i saw you visited my site so i came to “return the favor”.I’m attempting to find things to enhance my site!I suppose its ok to use a few of your ideas!!