相关链接
题目传送门:https://www.codechef.com/problems/GRAPHCNT
数据生成器:http://paste.ubuntu.com/24319212/
神犇题解Ⅰ:http://blog.csdn.net/a710128/article/details/49913553
神犇题解Ⅱ:http://www.cnblogs.com/meowww/p/6475952.html
解题报告
就是支配树的板题?
我们可以用Lengauer Tarjan算法在$O(n \alpha (n))$的时间复杂度内解决这个问题
也可以求出所有的半支配点,然后用灭绝树来搞,时间复杂度:$O(n \log n)$
另外之前我还看到一种非常鬼畜地LCT+灭绝树地做法,时间复杂度跑起来像:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 1500009; int n,m; 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; } class Dominator_Tree{ int dom[N],pre[N],head[N],nxt[M],to[M],que[N],anc[N]; int dfs_cnt,dfn[N],idom[N],semi[N],bst[N],ufs[N],sz[N]; public: inline void AddEdge(int u, int v) { AddEdge(head, u, v); AddEdge(pre, v, u); } inline void build() { DFS(1); for (int i=dfs_cnt,w;w=que[i],i>1;i--) { for (int j=pre[w];j;j=nxt[j]) { if (dfn[to[j]]) { update(to[j]); if (dfn[semi[bst[to[j]]]] < dfn[semi[w]]) semi[w] = semi[bst[to[j]]]; } } AddEdge(dom, semi[w], w); ufs[w] = anc[w]; w = que[i-1]; for (int j=dom[w];j;j=nxt[j]) { update(to[j]); if (semi[bst[to[j]]] == w) idom[to[j]] = w; else idom[to[j]] = bst[to[j]]; } } for (int i=2,w;w=que[i],i<=dfs_cnt;i++) idom[w] = ((idom[w] == semi[w])? idom[w]: idom[idom[w]]); } inline LL solve() { LL ret = dfs_cnt * (dfs_cnt - 1ll) / 2ll; for (int i=dfs_cnt,w;w=que[i],i>1;i--) { if (++sz[w], idom[w] != 1) sz[idom[w]] += sz[w]; else ret -= (sz[w] - 1ll) * sz[w] / 2ll; } return ret; } private: inline void AddEdge(int *arr, int u, int v) { static int E = 1; to[++E] = v; nxt[E] = arr[u]; arr[u] = E; } void DFS(int w) { dfn[w] = ++dfs_cnt; que[dfs_cnt] = w; bst[w] = semi[w] = ufs[w] = w; for (int i=head[w];i;i=nxt[i]) if (!dfn[to[i]]) anc[to[i]] = w, DFS(to[i]); } int update(int w) { if (ufs[w] == w) return w; int tmp = update(ufs[w]); if (dfn[semi[bst[ufs[w]]]] < dfn[semi[bst[w]]]) bst[w] = bst[ufs[w]]; return ufs[w] = tmp; } }DMT; int main() { n = read(); m = read(); for (int i=1,u,v;i<=m;i++) { u = read(); v = read(); DMT.AddEdge(u, v); } DMT.build(); cout<<DMT.solve(); return 0; }
865507 942853Water-resistant our wales in advance of when numerous planking. The certain wales surely are a selection of heavy duty snowboards that this height ones would be exactly the same in principle as a new shell planking having said that with significantly much more height to help you thrust outward within the evening planking. planking 143676
834195 79373This design is wicked! You certainly know how to keep a reader entertained. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Excellent job. I really loved what you had to say, and more than that, how you presented it. Too cool! 151835
442642 719207Thanks for taking the time to discuss this subject. I truly appreciate it. Ill stick a link of this entry in my blog. 332133
526849 700326dog grooming is the specialty of my sister, she actually loves grooming every dog in our house 193944
191392 814827 I discovered your blog internet site on google and check a couple of of your early posts. Continue to maintain up the extremely great operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading a lot more from you later on! 45876
458334 784176If you are still on the fence: grab your favorite earphones, head down to a Finest Buy and ask to plug them into a Zune then an iPod and see which 1 sounds better to you, and which interface makes you smile a lot more. Then you will know which is correct for you. 651350
390598 199478Hello! Nice post! Please do keep us posted when we can see a follow up! 734575
I believe this is one of the such a lot vital information for me.
And i am glad studying your article. But should commentary on some basic things,
The website taste is great, the articles is
really great : D. Just right process, cheers
749903 902361Normally I do not learn post on blogs, nevertheless I would like to say that this write-up quite pressured me to look at and do so! Your writing style has been surprised me. Thank you, quite wonderful post. 765604
Thanks for the good writeup. It in truth was a amusement account it.
Glance advanced to more added agreeable from
you! By the way, how could we communicate?
882168 417248Your talent is actually appreciated!! Thank you. You saved me a lot of frustration. I switched from Joomla to Drupal towards the WordPress platform and Ive fully embraced WordPress. Its so significantly easier and easier to tweak. Anyway, thanks again. Awesome domain! 290163
You ought to be a part of a contest for one of the best websites online.
I most certainly will recommend this blog!
351698 394649I added this article to my favorites and strategy to return to digest more soon. Its straightforward to read and recognize as nicely as intelligent. I truly enjoyed my first read by means of of this article. 694432
I for all time emailed this weblog post page to all my associates,
since if like to read it then my friends will too.
Greetings! This is my first visit to your blog! We are a
team of volunteers and starting a new project in a community in the same niche.
Your blog provided us useful information to work
on. You have done a extraordinary job!
It’s genuinely very complicated in this active life to listen news on TV,
so I simply use world wide web for that purpose, and take the most up-to-date information.
I’m curious to find out what blog platform you happen to be utilizing?
I’m experiencing some small security issues with my latest website and I’d like to
find something more secure. Do you have any recommendations?
I’ve learn some good stuff here. Certainly worth bookmarking for revisiting.
I surprise how much effort you place to create
any such fantastic informative site.
Undeniably believe that which you stated. Your favorite justification seemed to be on the internet the
simplest thing to be aware of. I say to you, I definitely get annoyed while people
think about worries that they plainly don’t know about. You
managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people can take a signal.
Will likely be back to get more. Thanks
Why people still use to read news papers when in this technological world all is accessible on net?
Just want to say your article is as astounding.
The clearness in your post is just excellent and i can assume you’re
an expert on this subject. Well with your permission allow me to grab your feed to keep
updated with forthcoming post. Thanks a million and please keep up
the enjoyable work.
obviously like your web site but you have to take a look
at the spelling on several of your posts. A number of them
are rife with spelling problems and I find it very bothersome to tell the truth nevertheless I will definitely
come again again.
I think what you posted made a lot of sense.
But, think on this, suppose you added a little information? I mean, I don’t wish to tell you
how to run your website, however what if you added something that makes people want more?
I mean 【CodeChef GRAPHCNT】[May Challenge 2015] Counting on a directed graph – Qizy's Database is
kinda plain. You should look at Yahoo’s home page and note how
they write news titles to grab people to open the links. You
might add a related video or a picture or two to get readers excited about what you’ve got to say.
Just my opinion, it might bring your posts a little bit more interesting.
Perfectly pent content, Really enjoyed looking at.
I’m not sure exactly why but this blog is loading incredibly slow for me.
Is anyone else having this issue or is it a problem on my end?
I’ll check back later on and see if the problem still exists.
hey there and thank you for your info – I have certainly picked up anything
new from right here. I did however expertise
several technical issues using this web site, as I experienced to
reload the site many times previous to I could get it to load correctly.
I had been wondering if your hosting is OK? Not that I’m complaining, but sluggish loading instances times will very frequently
affect your placement in google and could damage your high quality score if ads
and marketing with Adwords. Well I am adding this RSS to my e-mail and can look out for much more of your respective exciting content.
Ensure that you update this again very soon.
Hello There. I found your blog using msn. This is a very well written article.
I will make sure to bookmark it and return to read more of
your useful info. Thanks for the post. I’ll certainly comeback.
Hello! I’m at work browsing your blog from my new iphone!
Just wanted to say I love reading through your blog and look forward to all your posts!
Keep up the outstanding work!
I do not know if it’s just me or if perhaps everyone else encountering problems with your blog.
It appears as if some of the written text in your content
are running off the screen. Can someone else please comment and let me know if this is happening
to them as well? This may be a problem with my web browser because I’ve had
this happen before. Many thanks
Your style is really unique compared to other people
I’ve read stuff from. Many thanks for posting when you have the opportunity, Guess I will just book mark this site.
Howdy! I know this is kind of off topic but I was wondering which blog platform are you using for
this site? I’m getting tired of WordPress because I’ve had issues with hackers and I’m looking at options for another platform.
I would be fantastic if you could point me in the direction of a good platform.
Hello 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 require any
html coding expertise to make your own blog? Any help would be greatly
appreciated!
Incredible quest there. What happened after? Good luck!
Just desire to say your article is as astonishing. The clarity in your post is just excellent and i
can assume you are an expert on this subject.
Well with your permission let me to grab your feed to keep
updated with forthcoming post. Thanks a million and please carry on the rewarding work.
Link exchange is nothing else but it is only placing the other person’s website link on your page at
suitable place and other person will also do same in favor of
you.
I don’t know if it’s just me or if perhaps
everyone else encountering issues with your website. It looks like some of the written text on your content are running off the screen. Can someone else please comment and
let me know if this is happening to them as well?
This could be a problem with my browser because I’ve had this happen previously.
Thank you
Its like you read my mind! You seem to know a lot about this, like you wrote the book in it or something. I think that you can do with a few pics to drive the message home a little bit, but instead of that, this is excellent blog. A great read. I’ll definitely be back.