相关链接
题目传送门：http://codeforces.com/contest/804/problem/C
解题报告
不难发现这货是个弦图
然后仔细想想，只要保证
在原图中，一个一个结点处理
所有处理过的结点组成一个连通块
就可以了
至于这样为什么是对的？
因为最小染色数很好确定，就是$\max(s_i)$
所以我们只需要求出染色方案数，所以只要染色随时是一个连通块就可以了
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 600009;
int n,m,ans,head[N],to[N],nxt[N],sz[N],col[N];
vector<int> vis[N],lst[N];
set<int> que[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) {
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 solve(int w, int f) {
int cur = 1;
for (int jj=0;jj<lst[w].size();jj++) {
int j = lst[w][jj];
if (!col[j]) {
while (!que[w].empty() && cur == *que[w].begin()) {
++cur;
que[w].erase(que[w].begin());
}
col[j] = cur;
for (int k=0;k<vis[j].size();k++) {
que[vis[j][k]].insert(cur);
}
}
}
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
solve(to[i], w);
}
}
}
int main() {
n = read(); m = read();
ans = 1;
for (int i=1;i<=n;i++) {
sz[i] = read();
ans = max(ans, sz[i]);
for (int j=1,p;j<=sz[i];j++) {
p = read();
vis[p].push_back(i);
lst[i].push_back(p);
}
}
for (int i=1;i<n;i++) {
AddEdge(read(), read());
}
solve(1, 1);
cout<<ans<<endl;
for (int i=1;i<=m;i++) {
printf("%d ",col[i]? col[i]: 1);
}
return 0;
}
哇塞，居然是沙发？留个名
Good post. I learn something totally new and challenging on sites I stumbleupon every day.
It will always be useful to read content from other authors and practice something from their sites.
Does your site have a contact page? I’m having a
tough time locating it but, I’d like to shoot you an email.
I’ve got some creative ideas for your blog you might be interested in hearing.
Either way, great website and I look forward to seeing it develop
over time.
Everything is very open with a clear description of the challenges.
It was really informative. Your site is extremely
helpful. Thank you for sharing!
Post writing is also a excitement, if you know then you can write
or else it is complex to write.
I am actually happy to glance at this blog posts which includes
plenty of useful facts, thanks for providing these kinds of
information.
Howdy, i read your blog from time to time and i own a similar one and i was just wondering if you get a lot of spam remarks?
If so how do you protect against it, any plugin or anything
you can suggest? I get so much lately it’s driving me crazy so
any support is very much appreciated.
Howdy! I just wish to offer you a huge thumbs up for your great information you have right here on this post.
I will be returning to your blog for more soon.
I have been surfing on-line more than three hours today, yet
I never found any fascinating article like yours. It’s beautiful value enough for me.
In my opinion, if all webmasters and bloggers made just right
content as you probably did, the web will likely be much more helpful than ever before.
Hello this is somewhat of off topic but I was wanting to know if blogs
use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding experience so
I wanted to get guidance from someone with experience.
Any help would be enormously appreciated!
Hi, Neat post. There is a problem together with your website in web explorer,
may test this? IE still is the marketplace chief
and a good element of other people will omit your great writing due to this problem.
We’re a group of volunteers and starting a new scheme in our community.
Your web site provided us with valuable info to work on. You have done a formidable job and our whole
community will be grateful to you.
I am truly grateful to the owner of this website who
has shared this fantastic article at at this place.
naturally like your website but you have to check the spelling on several of your posts.
Several of them are rife with spelling issues and I
find it very troublesome to tell the truth nevertheless I will certainly come back again.
certainly like your web site but you need to check the spelling on quite a few
of your posts. A number of them are rife with
spelling problems and I find it very bothersome to tell the
reality however I will certainly come back again.
Hi there, its nice piece of writing on the topic of media print, we all know media is
a wonderful source of data.
whoah this weblog is wonderful i love studying your posts.
Keep up the great work! You recognize, many individuals are searching round for this information, you
can aid them greatly.
It’s a pity you don’t have a donate button! I’d most
certainly donate to this fantastic blog! I suppose for now i’ll settle for book-marking and adding your RSS feed to my Google account.
I look forward to new updates and will share this website with my Facebook
group. Chat soon!
Hey there! I’ve been reading your website for a while now and finally got the courage to go ahead and give you a shout out from Austin Tx!
Just wanted to mention keep up the good job!
Great blog! Do you have any tips and hints for aspiring writers?
I’m planning to start my own website soon but I’m a little lost on everything.
Would you suggest starting with a free platform like WordPress or go for a paid option?
There are so many choices out there that I’m totally overwhelmed ..
Any recommendations? Kudos!
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 wish to suggest you few interesting things or
suggestions. Perhaps you can write next articles referring to this article.
I desire to read more things about it!
Greetings from Ohio! I’m bored at work so I decided to browse your blog on my iphone during lunch break.
I really like the knowledge you provide here and can’t wait to take a look when I get home.
I’m surprised at how fast your blog loaded on my phone ..
I’m not even using WIFI, just 3G .. Anyways, wonderful site!
It is appropriate time to make some plans for the future and it is time to
be happy. I have read this post and if I could I desire to suggest
you few interesting things or tips. Perhaps you could write next
articles referring to this article. I wish to read more things about it!
I am sure this post has touched all the internet people,
its really really fastidious paragraph on building up new website.
plenty of fish natalielise
Thank you for any other informative site. The
place else could I get that kind of info written in such a perfect
manner? I have a undertaking that I am just now running on, and I have been on the glance out for such info.
My spouse and I stumbled over here different website
and thought I should check things out. I like what I see so now i’m following you.
Look forward to looking into your web page for a second time.
It’s wonderful that you are getting thoughts from this
piece of writing as well as from our argument made at
this place.
This web site certainly has all of the info I
needed about this subject and didn’t know who to ask.
For most up-to-date information you have to pay a quick visit world wide web and
on web I found this website as a most excellent web page
for most up-to-date updates.
You made some really good points there. I looked on the web to learn more about the issue and found
most people will go along with your views on this website.
If some one needs expert view regarding running a blog
afterward i advise him/her to go to see this webpage, Keep up the
pleasant job. natalielise plenty of fish
Everything is very open with a very clear clarification of
the issues. It was definitely informative. Your site is extremely helpful.
Thanks for sharing!
Attractive section of content. I just stumbled upon your weblog and in accession capital to
assert that I get in fact enjoyed account your
blog posts. Any way I’ll be subscribing to your augment and even I achievement
you access consistently quickly.
My brother suggested I might like this web site.
He was totally right. This post actually made my day. You can not
imagine simply how much time I had spent for this info!
Thanks!
Hurrah! After all I got a weblog from where I know how to
truly get helpful data concerning my study and
knowledge.
Hey! Someone in my Facebook group shared this
website with us so I came to check it out. I’m definitely enjoying
the information. I’m bookmarking and will be tweeting this to
my followers! Superb blog and superb style and
design.
What’s up, I would like to subscribe for this blog to get most up-to-date updates, so
where can i do it please help out.
This is my first time go to see at here and i am truly
happy to read all at alone place.
Howdy! This post could not be written any better! Reading this post reminds me
of my good old room mate! He always kept talking about this.
I will forward this write-up to him. Fairly certain he will have a
good read. Thanks for sharing!
Howdy! This post could not be written much better!
Looking at this article reminds me of my previous roommate!
He continually kept preaching about this. I most certainly will
forward this information to him. Pretty sure he’ll have a
very good read. I appreciate you for sharing!
I could not resist commenting. Very well written!
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.
Very good blog post. I certainly love this website. Thanks!
This site was… how do I say it? Relevant!! Finally I have found something that helped me.
Many thanks!
I really like it when individuals get together
and share ideas. Great website, continue the
good work!
This paragraph will assist the internet visitors for
creating new blog or even a weblog from start to end.
It is not my first time to pay a quick visit this site, i am visiting this web
page dailly and get pleasant facts from here everyday.
Hey I am so grateful I found your blog page, I really found you by error,
while I was searching on Bing for something else, Anyhow I am here
now and would just like to say many thanks for a
tremendous post and a all round interesting blog (I also love the theme/design), I don’t have time to read through it
all at the moment but I have saved it and also added your RSS feeds, so when I have time I
will be back to read more, Please do keep up the great jo.
You’re so cool! I do not suppose I have read through anything like this before.
So nice to discover somebody with some genuine thoughts on this topic.
Really.. thanks for starting this up. This site is something that is required
on the web, someone with a bit of originality!
This iis my first time go to see at here and i am genuinmely
impressed to read everthing at one place.
First of all I would like to say wonderful
blog! I had a quick question which I’d like to ask if you don’t mind.
I was curious to know how you center yourself and clear your thoughts before writing.
I’ve had trouble clearing my mind in getting my ideas out.
I truly do enjoy writing but it just seems like the first 10 to 15 minutes tend to
be lost simply just trying to figure out how to begin. Any suggestions or tips?
Cheers!
Hi! I just wanted to ask if you ever have any problems 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 methods to stop hackers?
Hello! Do you use Twitter? I’d like to follow you if that would be
ok. I’m definitely enjoying your blog and look forward to new posts.
I was suggested this website by my cousin. I’m not sure whether this
post is written by him as nobody else know such detailed
about my problem. You’re wonderful! Thanks!
I am curious to find out what blog system you
are working with? I’m having some minor security problems with
my latest website and I would like to find something more safe.
Do you have any solutions?
Keep this going please, great job!
Useful information. Lucky me I discovered your site by chance,
and I’m shocked why this twist of fate didn’t happened
earlier! I bookmarked it.
We stumbled over here by a different web address and thought I may
as well check things out. I like what I see so now i am following you.
Look forward to finding out about your web page for a second time.
Awesome! Its genuinely awesome piece of writing, I have
got much clear idea regarding from this piece of writing.
Very good blog! Do you have any tips for aspiring writers?
I’m hoping to start my own site soon but I’m a little lost on everything.
Would you recommend starting with a free platform like
Wordpress or go for a paid option? There are so many options out there that I’m totally
overwhelmed .. Any ideas? Bless you!
Greate pieces. Keep writing such kind of information on your blog.
Im really impressed by it.
Hey there, You’ve performed a great job. I will definitely
digg it and in my view recommend to my friends.
I’m confident they will be benefited from this web site.
It’s remarkable to pay a visit this website and reading
the views of all mates about this article, while I
am also zealous of getting knowledge.
We absolutely love your blog and find many of your post’s to be
exactly I’m looking for. can you offer guest writers
to write content in your case? I wouldn’t mind producing a post or elaborating on a number of the subjects you write regarding here.
Again, awesome weblog!
Undeniably believe that which you said. Your favorite justification seemed to be on the web the simplest thing to be aware of.
I say to you, I definitely get annoyed while people think about worries that they just do not know about.
You managed to hit the nail upon the top and defined out
the whole thing without having side effect , people could take
a signal. Will probably be back to get more.
Thanks
Thankfulness to my father who told me on the topic of this weblog, this website is actually
remarkable.
Greate pieces. Keep posting such kind of info on your page.
Im really impressed by it.
Hey there, You have done a fantastic job. I’ll definitely digg it and in my opinion suggest
to my friends. I am confident they’ll be benefited from this website.
Every weekend i used to pay a visit this site, as i want enjoyment,
as this this site conations in fact pleasant funny information too.
Wow, this post is pleasant, my younger sister is analyzing such things, therefore I
am going to tell her.
It’s perfect time to make some plans for the future and it’s
time to be happy. I have read this post and if I could
I want to suggest you few interesting things or tips. Maybe
you can write next articles referring to this article.
I desire to read more things about it!
Thank you for any other informative web site. Where else could I
am getting that kind of info written in such an ideal method?
I have a challenge that I’m simply now working on, and I
have been at the glance out for such information.
Hi there, every time i used to check website posts here in the early
hours in the morning, because i enjoy to find out more and more.
fantastic post, very informative. I ponder why the other experts of this sector do
not notice this. You should proceed your writing. I’m confident,
you have a huge readers’ base already!
Hi there! Do you know if they make any plugins to help with SEO?
I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good gains.
If you know of any please share. Many thanks!
I’m not sure where you’re getting your info, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for wonderful info I was looking for this information for my mission.
My spouse and I absolutely love your blog and find many 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 creating a post or elaborating on a
few of the subjects you write with regards to here.
Again, awesome weblog!
Good information. Lucky me I recently found your website by accident
(stumbleupon). I’ve saved it for later!
Thank you for the good writeup. It in truth
was a enjoyment account it. Glance advanced to more delivered agreeable from you!
By the way, how can we keep in touch?
Quality posts is the crucial to interest the visitors
to pay a visit the site, that’s what this website is providing.
Hello! I’ve been following your website for a long time now
and finally got the courage to go ahead and give you a shout out from Huffman Texas!
Just wanted to mention keep up the great job!
I want to to thank you for this good read!! I certainly loved
every bit of it. I have you book-marked to check out new stuff you post…
It’s hard to find knowledgeable people on this topic, but you sound like you know what you’re talking about! Thanks
Normally I do not read article on blogs, however I wish to say that this write-up very pressured me to take
a look at and do it! Your writing style has been surprised me.
Thank you, very nice post.
When I initially commented I clicked the “Notify me when new comments are added”
checkbox and now each time a comment is added I get several e-mails with the same comment.
Is there any way you can remove people from that service?
Thanks a lot!
Hello this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if
you have to manually code with HTML. I’m starting a blog soon but have no coding know-how so I wanted to
get guidance from someone with experience. Any help would be enormously appreciated!
I always spent my half an hour to read this blog’s content daily along with a cup
of coffee.
Do you have a spam problem on this blog; I also am a blogger, and I was wanting to know your situation; we have created some nice methods and we
are looking to trade methods with other folks, please shoot me an email if interested.
This post gives clear idea designed for the new people of blogging,
that in fact how to do blogging and site-building.
Hello colleagues, nice article and nice arguments commented here, I am
truly enjoying by these.
Hi! I’ve been reading your weblog for a while now and
finally got the bravery to go ahead and give you a shout out from Porter Texas!
Just wanted to say keep up the fantastic work!
hi!,I really like your writing very a lot! proportion we communicate more approximately
your article on AOL? I require an expert in this space to solve my problem.
May be that’s you! Looking forward to see you.
fantastic issues altogether, you simply received a brand new
reader. What could you suggest about your put up that you made some days ago?
Any certain?
Excellent post. I was checking constantly this blog and I’m
impressed! Extremely helpful information specifically the last part 🙂 I care for such information a lot.
I was looking for this certain info for a long time.
Thank you and good luck.
Hi there colleagues, how is all, and what you want to
say concerning this piece of writing, in my view its genuinely awesome for me.
If some one wants to be updated with most up-to-date technologies therefore he must be pay a quick visit this web page and be up to date every day.
I every time used to read paragraph in news papers but now as I am a user of net thus from now I
am using net for articles, thanks to web.
Your place is valueble for me. Thanks!…
Muchos Gracias for your blog. Awesome.
Great blog post.Much thanks again. Really Great.