【Codeforces 802L】Send the Fool Further! (hard)

相关链接

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

212 thoughts to “【Codeforces 802L】Send the Fool Further! (hard)”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  37. I know this website provides quality dependent articles and
    other material, is there any other site which presents such information in quality?

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

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

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

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

Leave a Reply

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