参考例题：http://www.lydsy.com/JudgeOnline/problem.php?id=4530
#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;
}
Attractive portion of content. I just stumbled upon your blog and in accession capital to say that I acquire in fact loved account your blog posts.
Any way I will be subscribing on your augment and
even I success you access consistently rapidly.
Hmm it looks like your blog ate my first comment (it was super long) so I guess I’ll just sum it up what I submitted 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 suggestions for novice blog writers?
I’d definitely appreciate it.
Pretty! This was an extremely wonderful post. Many thanks for providing
this info.
I was recommended this web site via my cousin. I am now not positive whether
or not this post is written by means of him as nobody
else know such designated approximately my trouble. You’re incredible!
Thank you!
My brother suggested I might like this website. He was entirely right.
This post actually made my day. You can not imagine just how
much time I had spent for this information! Thanks!
Wonderful article! We are linking to this great post
on our website. Keep up the good writing.
I absolutely love your blog and find a lot of your post’s to be just what
I’m looking for. Does one offer guest writers to write content to
suit your needs? I wouldn’t mind producing a post or elaborating on many of the subjects you write about here.
Again, awesome website!
Hi there! I just wanted to ask if you ever have any trouble with hackers?
My last blog (wordpress) was hacked and I ended up losing a few months of hard
work due to no back up. Do you have any solutions to stop hackers?
My spouse and I stumbled over here coming
from a different website and thought I should
check things out. I like what I see so i am just following you.
Look forward to looking at your web page yet again.
If you are going for finest contents like myself, simply go to see this
web page all the time since it gives quality contents, thanks
I’m not sure where you are getting your information, but great topic.
I needs to spend some time learning much more or understanding more.
Thanks for fantastic info I was looking for this information for my mission.
Hello! Someone in my Facebook group shared this website with us so I came to give it a look.
I’m definitely enjoying the information. I’m book-marking and will be tweeting this to my followers!
Excellent blog and outstanding style and design.
It’s really a nice and useful piece of information. I am happy that
you simply shared this useful information with us. Please keep us informed like this.
Thank you for sharing.
Hey just wanted to give you a quick heads up. The text in your content
seem to be running off the screen in Firefox.
I’m not sure if this is a format issue or something to do with web browser compatibility but I figured
I’d post to let you know. The layout look great though!
Hope you get the problem resolved soon. Thanks
I’m curious to find out what blog system you’re using?
I’m having some small security problems with my latest website and I would like to find something
more risk-free. Do you have any solutions?
Wow! This blog looks exactly like my old one! It’s on a totally different topic but it has pretty
much the same layout and design. Outstanding choice of colors!
Thank you for some other great post. The place else may just anyone get that kind of information in such an ideal method of writing? I have a presentation subsequent week, and I’m at the look for such information.
For hottest news you have to visit world wide web and on the web I
found this website as a best website for latest updates.
You’ve made some good points there. I checked on the net
for more information about the issue and found most individuals will go along with your views
on this site.
Just wish to say your article is as surprising.
The clearness on your put up is simply cool and i can think
you are knowledgeable on this subject. Well with your permission allow me to take hold of
your RSS feed to keep up to date with impending post.
Thanks one million and please carry on the gratifying work.
Terrific article! That is the type of info that should be
shared around the net. Shame on Google for not positioning this
publish upper! Come on over and seek advice from my web
site . Thank you =)
Hi to all, how is all, I think every one is getting more from this website, and your
views are good in support of new users.
Simply a smiling visitor here to share the love (:, btw great design. “Make the most of your regrets… . To regret deeply is to live afresh.” by Henry David Thoreau.
I need to say your site is really helpful I also love the theme, its amazing!