相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4530
解题报告
这题LCT是可以做的
但因为本题没有要求强制在线
所以我们可以用并查集来维护连通性,再用线段树合并来支持支持DFS序的区间询问
总的时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = N * 21; int n, m, vis[N], head[N], nxt[N], to[N]; int dep[N], beg[N], out[N], sz[N], fa[N]; struct Data{ int t, x, y; inline Data() { } inline Data(bool a, int b, int c):t(a), x(b), y(c) { } }opt[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline void DFS(int w, int f) { static int D = 0; vis[w] = 1; beg[w] = ++D; dep[w] = dep[f] + 1; for (int i = head[w]; i; i = nxt[i]) { if (to[i] != f) { DFS(to[i], w); } } out[w] = D; } inline int find(int x) { return fa[x] == x? x: fa[x] = find(fa[x]); } class SegmentTree{ int cnt, ch[M][2], sum[M], root[N]; public: inline void insert(int p, int v) { insert(root[p], 1, n, v); } inline void merge(int a, int b) { root[a] = Merge(root[a], root[b]); } inline int query(int p, int l, int r) { return query(root[p], 1, n, l, r); } private: inline int Merge(int a, int b) { if (!a || !b) { return a + b; } else { sum[a] += sum[b]; ch[a][0] = Merge(ch[a][0], ch[b][0]); ch[a][1] = Merge(ch[a][1], ch[b][1]); return a; } } inline void insert(int &w, int l, int r, int p) { sum[w = ++cnt] = 1; if (l < r) { int mid = l + r + 1 >> 1; if (p < mid) { insert(ch[w][0], l, mid - 1, p); } else { insert(ch[w][1], mid, r, p); } } } inline int query(int w, int l, int r, int L, int R) { if (!w) { return 0; } else if (L <= l && r <= R) { return sum[w]; } else { int mid = l + r + 1 >> 1, ret = 0; ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0; ret += mid <= R? query(ch[w][1], mid, r, L, R): 0; return ret; } } }SGT; int main() { n = read(); m = read(); for (int i = 1; i <= m; i++) { char cmd[3]; scanf("%s", cmd); int u = read(), v = read(); if (cmd[0] == 'A') { AddEdge(u, v); } opt[i] = Data(cmd[0] == 'A', u, v); } for (int i = 1; i <= n; i++) { if (!vis[i]) { DFS(i, i); } } for (int i = 1; i <= n; i++) { sz[i] = 1; fa[i] = i; SGT.insert(i, beg[i]); } for (int i = 1; i <= m; i++) { int u = opt[i].x, v = opt[i].y; if (opt[i].t == 1) { SGT.merge(find(u), find(v)); sz[find(u)] += sz[find(v)]; fa[find(v)] = find(u); } else { if (dep[u] < dep[v]) { swap(u, v); } int p1 = SGT.query(find(u), beg[u], out[u]); int p2 = sz[find(u)] - p1; printf("%lld\n", (LL)p1 * p2); } } return 0; }
好文章!666,学习了
465739 356918Some truly nice stuff on this web site , I like it. 433879
882869 195158I like this blog quite considerably so a lot very good info . 745322
690247 797870Very informative post. Your current Site style is awesome as properly! 623892
305905 962534Hey, you?re the goto expert. Thanks for haingng out here. 875312
203946 533355Hey. Extremely nice web web site!! Man .. Excellent .. Wonderful .. Ill bookmark this web site and take the feeds alsoI am pleased to locate so a lot valuable data here within the article. Thanks for sharing 425447
191786 766774It was any exhilaration discovering your website yesterday. I arrived here nowadays hunting new points. I was not necessarily frustrated. Your suggestions after new approaches on this thing have been beneficial plus an superb assistance to personally. We appreciate you leaving out time to write out these items and then for revealing your thoughts. 419478
520160 92577Yay google is my king helped me to uncover this outstanding website! . 299103
941669 239038Found your weblog and decided to have a study on it, not what I typically do, but this blog is wonderful. Awesome to see a web site thats not spammed, and in fact makes some sense. Anyway, wonderful write up. 783382
788936 143114Howdy! I just want to give an enormous thumbs up for the fantastic information you might have here on this post. I will likely be coming back to your weblog for far more soon. 239475
197729 289549There exist a couple of many different distinct levels among the California Weight loss program and each and every a person is pretty important. You are procedure stands out as the the actual giving up with all the power. weight loss 788521
What’s up to every one, for the reason that I am really
eager of reading this webpage’s post to be updated daily.
It consists of good data.
649330 610842I respect your piece of work, appreciate it for all the interesting content material . 31999
After exploring a few of the articles on your web site, I truly appreciate your
way of blogging. I book marked it to my bookmark webpage list
and will be checking back in the near future.
Please visit my website as well and let me know your opinion.
143434 829835Just wanna comment that you have a very good internet site , I enjoy the style it really stands out. 130994
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 site to come back in the future.
Cheers
Simply want to say your article is as surprising.
The clarity in your post is simply excellent
and i could assume you are an expert on this subject.
Well with your permission let me to grab your feed to keep up to date with forthcoming post.
Thanks a million and please carry on the gratifying work.
You need to take part in a contest for one of the greatest blogs on the web.
I most certainly will recommend this website!
Remarkable! Its actually amazing article, I have got much clear idea regarding from this piece of
writing.
Great website. Lots of useful info here. I am sending
it to some buddies ans also sharing in delicious.
And of course, thank you in your sweat!
Thanks for the good writeup. It in fact was a entertainment account
it. Glance advanced to far delivered agreeable from you!
However, how could we keep in touch?
My developer is trying to persuade me to move
to .net from PHP. I have always disliked the idea because of
the expenses. But he’s tryiong none the less. I’ve been using WordPress on numerous websites
for about a year and am worried about switching to another platform.
I have heard fantastic things about blogengine.net.
Is there a way I can import all my wordpress content into it?
Any help would be really appreciated!
Hey There. I found your weblog the usage of msn. That is an extremely well written article.
I will be sure to bookmark it and come back
to read extra of your useful information. Thanks for the post.
I’ll definitely comeback.
Hey very interesting blog!
Hi, this weekend is fastidious in support of me,
because this point in time i am reading this fantastic informative paragraph here at my
residence.
I could not resist commenting. Very well written!
After exploring a handful of the blog articles on your web site, I really appreciate your technique
of writing a blog. I added it to my bookmark webpage list and will be checking
back in the near future. Please visit my website as
well and tell me what you think.
I enjoy the efforts you have put in this, appreciate it for all the great posts.
It is appropriate time to make some plans for the future and it’s time to be happy. I’ve read this post and if I could I desire to suggest you some interesting things or tips. Maybe you can write next articles referring to this article. I want to read more things about it!
I used to be able to find good information from your content.
This article presents clear idea in favor
of the new users of blogging, that truly how to do blogging.
Hello! Quick question that’s totally off topic. Do you know how
to make your site mobile friendly? My web site looks weird when browsing from my iphone4.
I’m trying to find a theme or plugin that might be able to
fix this issue. If you have any suggestions, please share.
Thank you!
Hello, its pleasant paragraph regarding media print, we all
be aware of media is a fantastic source of data.
It’s a shame you don’t have a donate button! I’d certainly donate to this
outstanding blog! I guess for now i’ll settle for bookmarking and adding your
RSS feed to my Google account. I look forward to fresh updates and will talk about this
blog with my Facebook group. Chat soon!
At this moment I am going to do my breakfast, afterward having my breakfast coming yet
again to read more news.
I visited multiple web sites but the audio feature for audio
songs present at this web page is genuinely superb.
I am not sure where you are getting your info, but good topic.
I needs to spend some time learning much more or understanding more.
Thanks for great information I was looking for this information for my mission.
Hello! Someone in my Myspace group shared this site with us so I came to
check it out. I’m definitely loving the information. I’m bookmarking and will be tweeting this
to my followers! Superb blog and superb style and design.
These are truly enormous ideas in concerning blogging.
You have touched some nice points here. Any way keep up wrinting.
Someone essentially help to make seriously articles I would state. This is the very first time I frequented your website page and thus far? I amazed with the research you made to make this particular publish extraordinary. Excellent job!