题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3569
数据生成器：http://paste.ubuntu.com/23227745/
这个题，是我到目前为止，做过的最妙的一道题
没有之一
给每一个非树边搞一个权值
然后亦或到它所覆盖的每一条树边上去
考虑不联通的情况：删掉了一条树边和所有覆盖他的非树边
及一个子集的亦或和为0
于是像求线性基一样，判一下是否线性无关即可
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100000+9;
const int M = 1000000+9;
const int MOD = 9999971;
const int SGZ = 40;
int head[N],nxt[M],to[M],n,m,q,val[M];
int vis[N],c[SGZ],cnt,bas[SGZ],sym[N];
inline int read(){
char c=getchar(); int ret=0,f=1;
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 Add_Edge(int u, int v) {
static int T = 1;
to[++T] = v; nxt[T] = head[u]; head[u] = T;
to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
void DFS1(int w, int f) {
vis[w] = 1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (vis[to[i]]) {
int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W;
sym[w] ^= W; sym[to[i]] ^= W;
} else DFS1(to[i],w);
}
}
void DFS2(int w, int f) {
for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i])
DFS2(to[i], w), val[i] ^= sym[to[i]],
val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]];
}
inline bool update(int w) {
for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) {
if (!bas[i]) {bas[i] = tmp; return false;}
else {tmp ^= bas[i]; if (!tmp) return true;}
} return val[w]?false:true;
}
int main(){
srand(9999971); n = read(); m = read();
for (int i=1;i<=m;i++) Add_Edge(read(),read());
DFS1(1,1); DFS2(1,1);
for (int q=read(),k,tag;q;q--) {
k = read(); tag = 1; memset(bas,0,sizeof(bas));
for (int i=1;i<=k;i++) c[i] = read()^cnt;
for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0;
if (tag) puts("Connected"), cnt++;
}
return 0;
}
楼下是疯子。哈哈
I really like your blog.. very nice colors & theme.
Did you make this website yourself or did you hire someone to do it for you?
Plz respond as I’m looking to design my own blog and would like
to find out where u got this from. thank you
Excellent post. I was checking constantly this blog
and I am impressed! Extremely useful info particularly the last part 🙂 I care
for such information much. I was seeking this certain info for a long time.
Thank you and good luck.
It is not my first time to go to see this site, i am browsing this web page dailly and obtain good facts
from here every day.
Great blog here! Also your site loads up fast!
What host are you using? Can I get your affiliate link to your host?
I wish my web site loaded up as quickly as yours lol
Hi there, I do believe your web site could possibly be having web browser compatibility issues.
Whenever I look at your web site in Safari, it looks fine however when opening in I.E., it has some overlapping issues.
I simply wanted to give you a quick heads up! Other than that, excellent blog!
I used to be suggested this blog through my cousin. I
am not sure whether or not this post is written via him as no one else know such
detailed approximately my problem. You are wonderful! Thanks!
Oh my goodness! Incredible article dude! Thanks, However I am going through problems with
your RSS. I don’t know why I cannot subscribe to it.
Is there anybody else having identical RSS issues? Anybody who knows the solution will
you kindly respond? Thanks!!
Hi! I’m at work surfing around your blog from my new iphone 3gs!
Just wanted to say I love reading through
your blog and look forward to all your posts! Carry on the fantastic work!
I believe what you wrote was very logical. But, think on this, what
if you were to write a awesome headline? I ain’t suggesting your content is not good.,
but suppose you added a title that makes people want more?
I mean 【BZOJ 3569】DZY Loves Chinese II – Qizy's Database is kinda
boring. You might look at Yahoo’s home page and see how
they create post headlines to grab viewers interested.
You might add a related video or a related picture or two to grab
readers excited about what you’ve got to say. Just my opinion, it would make your posts a little livelier.
You’re so interesting! I don’t believe I have read anything
like this before. So good to discover another person with
a few original thoughts on this topic. Seriously..
thank you for starting this up. This site is something that is needed on the internet, someone with a bit of
originality!
What’s up, I want to subscribe for this webpage to take
newest updates, thus where can i do it please help out.
Hi there would you mind stating which blog platform you’re working with?
I’m looking to start my own blog in the near future but I’m having
a tough time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design and style seems different then most blogs and I’m looking for something completely unique.
P.S My apologies for getting off-topic but I had to ask!
Hello, I check your blog regularly. Your story-telling style is awesome, keep up the
good work!
Hmm it appears like your website ate my first comment (it was extremely long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I as well am an aspiring blog blogger but I’m still new to the
whole thing. Do you have any helpful hints for inexperienced blog writers?
I’d definitely appreciate it.
Hey there! I’m at work surfing around your blog from
my new iphone 3gs! Just wanted to say I love reading through
your blog and look forward to all your posts! Carry on the outstanding work!
I like the helpful info you provide in your articles.
I’ll bookmark your blog and check again here frequently.
I’m quite certain I’ll learn a lot of new stuff right here!
Best of luck for the next!
You can definitely see your enthusiasm in the work you write.
The sector hopes for even more passionate writers like you who are not afraid to say how they
believe. Always follow your heart.
each time i used to read smaller articles or reviews which as well clear their motive,
and that is also happening with this article which I am reading at this place.
Hey there! Quick question that’s entirely off topic. Do you know how to make your site mobile friendly?
My blog looks weird when browsing from my iphone4.
I’m trying to find a template or plugin that might be able to resolve this problem.
If you have any recommendations, please share.
Appreciate it!
What’s up, every time i used to check website posts here early in the morning, as i love to learn more and more.
Pretty nice post. I simply stumbled upon your weblog and wished to mention that
I have truly loved browsing your blog posts. After all I’ll be subscribing on your rss feed
and I am hoping you write again soon! pof natalielise
Thank you a bunch for sharing this with all people you actually know what you are speaking approximately!
Bookmarked. Kindly additionally talk over with
my website =). We will have a hyperlink change agreement among us pof natalielise
Hello there, I found your blog by means of Google at the same
time as looking for a comparable matter, your website came
up, it appears to be like good. I have bookmarked it in my google bookmarks.
Hi there, just become alert to your blog through Google, and found that it is truly informative.
I am gonna watch out for brussels. I will appreciate if you happen to continue this in future.
Numerous other people will be benefited from your writing.
Cheers! plenty of fish natalielise
Good way of describing, and good post to get
information on the topic of my presentation topic, which i am going
to deliver in college.
Right now it seems like Expression Engine is the top blogging platform out there right now.
(from what I’ve read) Is that what you are using on your blog?
Link exchange is nothing else but it is just placing the other person’s
web site link on your page at proper place and other person will also do similar in support of you.
I must thank you for the efforts you have put in writing this
site. I’m hoping to check out the same high-grade blog posts from you later on as well.
In truth, your creative writing abilities has encouraged
me to get my own, personal site now 😉
You ought to take part in a contest for one of the greatest sites on the internet.
I’m going to highly recommend this blog!
My spouse and I stumbled over here different page and thought I might as
well check things out. I like what I see so now i’m following you.
Look forward to looking into your web page repeatedly.
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 throw away your intelligence on just posting
videos to your site when you could be giving us
something enlightening to read?
I am regular reader, how are you everybody? This piece
of writing posted at this web page is actually pleasant.
I don’t even know the way I ended up right here, however I believed this put
up was once great. I do not recognize who you’re but certainly you are going
to a famous blogger if you happen to are not already. Cheers!
I read this article fully concerning the comparison of hottest and previous technologies,
it’s awesome article.
Hi! I could have sworn I’ve been to this blog
before but after browsing through some of the posts I realized it’s new
to me. Anyways, I’m certainly happy I discovered it and I’ll be bookmarking
it and checking back often!
It’s enormous that you are getting ideas from this post as well as from our discussion made here.
Fantastic items from you, man. I’ve take into account your stuff prior
to and you’re just too fantastic. I really like what you’ve acquired right
here, certainly like what you are stating and the best way by which you assert it.
You make it enjoyable and you continue to take care of to keep it sensible.
I can’t wait to read much more from you. This is really a terrific site.
What’s up to all, the contents existing at this site are truly awesome for people knowledge, well, keep up the nice work fellows.
I’m impressed, I must say. Rarely do I come across a blog that’s equally educative and interesting, and without
a doubt, you’ve hit the nail on the head.
The issue is something that too few folks are speaking intelligently about.
I am very happy I found this in my search for something concerning
this.
If some one desires expert view concerning running a blog then i advise him/her to pay a
visit this web site, Keep up the pleasant work.
Thank you for some other informative blog. The place else may I get that type of information written in such a perfect manner?
I have a challenge that I’m just now working on, and
I’ve been at the glance out for such information.
You’ve made some decent points there. I checked on the internet for additional information about the issue and found most
individuals will go along with your views on this web
site.
You’re so awesome! I don’t suppose I’ve read anything like this before.
So nice to discover somebody with original thoughts on this issue.
Really.. many thanks for starting this up.
This web site is one thing that is needed on the web, someone with
a bit of originality!
We stumbled over here from a different page and thought
I may as well check things out. I like what I see so
now i’m following you. Look forward to checking out your web page repeatedly.
Hi there, I enjoy reading through your post. I wanted
to write a little comment to support you.
Yesterday, while I was at work, my sister stole my apple ipad
and tested to see if it can survive a forty foot drop, just so she can be a youtube
sensation. My apple ipad is now destroyed and she
has 83 views. I know this is totally off topic but I had to share it with someone!
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 feedback would be greatly appreciated.
It is perfect time to make a few plans for the longer
term and it’s time to be happy. I’ve read this submit and if I may I wish to recommend you some fascinating issues or
suggestions. Perhaps you could write subsequent articles relating to this article.
I wish to learn even more issues approximately
it!
This is the right site for anyone who hopes to understand this topic.
You realize so much its almost tough to argue with you (not that I really will need to…HaHa).
You certainly put a brand new spin on a topic which has
been discussed for decades. Wonderful stuff, just wonderful!
I’m not sure where you’re getting your info, but good
topic. I needs to spend some time learning much more or understanding
more. Thanks for magnificent info I was looking for this info for my mission.
I have read so many articles about the blogger lovers however this
piece of writing is truly a nice paragraph, keep
it up.
Having read this I believed it was extremely enlightening.
I appreciate you taking the time and energy to put this content together.
I once again find myself personally spending
a significant amount of time both reading and leaving comments.
But so what, it was still worthwhile!
Awesome! Its really remarkable piece of writing, I have got
much clear idea regarding from this piece of writing.
This is very interesting, You’re a very skilled blogger.
I have joined your rss feed and look forward to seeking more of your great post.
Also, I have shared your website in my social
networks!
If you are going for best contents like myself, simply pay a visit this web page all the time because it
provides feature contents, thanks
I’m not sure exactly why but this weblog 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.
Hi! I know this is kinda off topic but I was wondering if you knew where
I could locate a captcha plugin for my comment form? I’m using
the same blog platform as yours and I’m having problems finding one?
Thanks a lot!
I am not sure where you are getting your information, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for magnificent info I was looking for this info for my
mission.
This is the right web site for anyone who wishes to find out about this topic.
You know a whole lot its almost hard to argue with you (not
that I personally would want to…HaHa). You certainly put a
fresh spin on a subject that’s been discussed for decades. Great stuff, just excellent!
Excellent beat ! I wish to apprentice while you amend your site, how could i
subscribe for a blog web site? The account helped me a acceptable
deal. I had been tiny bit acquainted of this your broadcast provided
bright clear concept
Greetings! Very useful advice in this particular article!
It’s the little changes that make the most important changes.
Thanks a lot for sharing!
Howdy! Would you mind if I share your blog with my twitter group?
There’s a lot of folks that I think would really enjoy your content.
Please let me know. Cheers
Thanks very nice blog!
An impressive share! I have just forwarded this onto a colleague who has been doing a
little research on this. And he actually ordered me dinner due to the fact that I found it for him…
lol. So allow me to reword this…. Thanks for the meal!!
But yeah, thanks for spending time to discuss this issue here
on your internet site.
hi!,I like your writing so so much! proportion we
keep up a correspondence more approximately your post on AOL?
I need a specialist in this space to unravel my problem.
Maybe that is you! Taking a look forward to see you.
Greetings from Ohio! I’m bored to death at work so I
decided to browse your website on my iphone during lunch break.
I really like the information you provide here and can’t wait to take a look when I get home.
I’m surprised at how quick your blog loaded on my mobile ..
I’m not even using WIFI, just 3G .. Anyhow, superb blog!
What’s up friends, its enormous post on the topic of tutoringand completely
defined, keep it up all the time.
I think this is one of the most important information for me.
And i am glad reading your article. But should remark on some general things, The site style is wonderful, the articles is really great :
D. Good job, cheers
Hello, this weekend is fastidious designed for me, because this moment i am reading
this wonderful educational piece of writing here at my home.
each time i used to read smaller articles or reviews that as well clear their motive,
and that is also happening with this article which I am reading
at this time.
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my newest twitter updates.
I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience
with something like this. Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your new updates.
Hmm it seems like your blog ate my first comment
(it was extremely 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 blogger but I’m still new to the whole thing.
Do you have any tips for novice blog writers? I’d genuinely appreciate it.
What’s Happening i’m new to this, I stumbled upon this I’ve discovered It absolutely
helpful and it has aided me out loads. I hope to give
a contribution & help different users like its aided me.
Great job.
Hi would you mind sharing which blog platform you’re using?
I’m looking to start my own blog in the near future but I’m having a hard time making
a decision between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different then most blogs and I’m looking for
something completely unique. P.S Sorry for being off-topic but I had to
ask!
I really like your blog.. very nice colors & theme. Did you design this website yourself or did you hire someone to do it for you?
Plz reply as I’m looking to create my own blog and would like to find out where u got this from.
many thanks
Thank you for sharing excellent informations. Your site is very cool. I’m impressed by the details that you’ve on this site. It reveals how nicely you perceive this subject. Bookmarked this website page, will come back for extra articles. You, my pal, ROCK! I found just the information I already searched all over the place and simply could not come across. What an ideal website.
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 months of hard work due
to no backup. Do you have any solutions to prevent hackers?
I got this site from my buddy who shared with me
about this site and now this time I am browsing this web page and
reading very informative content at this time.
Hello! Quick question that’s completely off topic. Do you
know how to make your site mobile friendly? My site looks weird
when browsing from my iphone. I’m trying to find a template or plugin that might be able to fix this problem.
If you have any suggestions, please share. Thank you!
Pretty! This was an extremely wonderful post. Thanks for providing these details.
We absolutely love your blog and find almost all of your post’s to be precisely what I’m looking for.
Would you offer guest writers to write content available for you?
I wouldn’t mind creating a post or elaborating on many of
the subjects you write concerning here. Again, awesome web site!
I really like your blog.. very nice colors & theme.
Did you create this website yourself or did you hire someone to do it for you?
Plz reply as I’m looking to design my own blog and would like to find out
where u got this from. thanks a lot
This is very interesting, You are a very skilled blogger.
I have joined your rss feed and look forward to seeking more of your excellent post.
Also, I’ve shared your website in my social networks!
We’re a group of volunteers and opening a new scheme in our community.
Your web site provided us with valuable info to work on. You’ve done an impressive job and our whole community will be grateful to you.
Wonderful goods from you, man. I’ve understand your
stuff previous to and you are just extremely magnificent.
I actually like what you’ve acquired here, really like what you’re saying and the way in which you say it.
You make it enjoyable and you still take care of to keep it smart.
I can not wait to read far more from you. This is actually a terrific website.
I’m not that much of a internet reader to be honest but your blogs really nice, keep it up! I’ll go ahead and bookmark your site to come back later on. Cheers
Hello! Do you use Twitter? I’d like to follow you if that would be okay.
I’m definitely enjoying your blog and look forward to new updates.
When someone writes an post he/she retains the idea of a user in his/her mind that how a user can know it.
So that’s why this paragraph is amazing. Thanks!