相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3926
神犇题解：http://wjmzbmr.com/archives/zjoi-2015-day-1题解/
解题报告
陈老师的语文真刺激！
把叶节点最多只有20个这个条件埋得那么深 QwQ
一开始以为那个条件意思是度数不超过20，于是想边分治，后来都想到”万径人踪灭”去了……
考虑树上每一条路径，至少存在一个叶子结点，使得将该叶子结点作为根后，这条路径上的结点深度递减
于是对于每一个叶节点都DFS一遍，然后建广义后缀自动机
广义自动机的话，直接看这份代码就好吧！
或者想全面学习的话，可以看这里：传送门
另外，这题据陈老师说，后缀数组也可以做
但我不会啊，跪求神犇带 _(:з」∠)_
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200000+9;
const int M = 2000000;
const int C = 10;
int n,c,col[N],head[N],to[N],nxt[N],in[N];
class Suffix_Automaton{
int ch[M][C],pre[M],len[M],cnt;
public:
inline int insert(int last, int t) {
int w = ++cnt; len[w] = len[last] + 1; pre[0] = -1;
for (;~last&&!ch[last][t];last=pre[last]) ch[last][t] = w;
if (~last) {
if (len[ch[last][t]] == len[last] + 1) {
pre[w] = ch[last][t];
} else {
int nw = ++cnt, tmp = ch[last][t];
len[nw] = len[last] + 1;
pre[nw] = pre[tmp]; pre[tmp] = pre[w] = nw;
memcpy(ch[nw],ch[tmp],sizeof(ch[nw]));
for (;~last&&ch[last][t]==tmp;last=pre[last]) ch[last][t] = nw;
}
} return w;
}
inline LL solve() {
LL ret = 0;
for (int i=1;i<=cnt;i++)
ret += len[i] - len[pre[i]];
return ret;
}
}SAM;
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 Add_Edge(int u, int v) {
static int E = 1; in[u]++; in[v]++;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
void DFS(int w, int f, int s) {
int rt = SAM.insert(s, col[w]);
for (int i=head[w];i;i=nxt[i])
if (to[i] != f) DFS(to[i], w, rt);
}
int main() {
n = read(); c = read();
for (int i=1;i<=n;i++) col[i] = read();
for (int i=1;i<n;i++) Add_Edge(read(),read());
for (int i=1;i<=n;i++) if (in[i] == 1) DFS(i, i, 0);
printf("%lld\n",SAM.solve());
return 0;
}
楼下是疯子。哈哈
You should take part in a contest for one of the highest quality sites on the internet.
I’m going to highly recommend this website!
Hey there! I could have sworn I’ve been to this website before but after checking through some of the post
I realized it’s new to me. Anyways, I’m definitely glad
I found it and I’ll be bookmarking and checking back frequently!
It’s awesome to pay a visit this site and reading the views of all
mates concerning this piece of writing, while I am also
keen of getting know-how.
My brother recommended I may like this web site. He was totally right.
This put up actually made my day. You can not imagine just
how much time I had spent for this info! Thank you!
If you desire to obtain a great deal from this paragraph then you have to apply these methods to
your won web site.
Aw, this was a very good post. Taking the time
and actual effort to create a very good article… but what can I say… I procrastinate
a lot and don’t manage to get nearly anything done.
Hello There. I found your blog using msn. This is a very well written article.
I’ll be sure to bookmark it and return to read more of your useful info.
Thanks for the post. I will definitely comeback.
We’re a group of volunteers and opening a new scheme in our community.
Your site provided us with helpful info to work on. You have performed a formidable activity and our whole group shall be grateful to you.
Hi, i think that i saw you visited my web site so i came
to “return the favor”.I’m attempting to find things to enhance my website!I suppose its ok to use
some of your ideas!!
Hello my friend! I wish to say that this post is amazing, nice written and come
with almost all important infos. I’d like to look more posts like this .
I have to thank you for the efforts you’ve put in writing this blog.
I really hope to check out the same high-grade content from you later on as well.
In fact, your creative writing abilities has inspired me to get my own, personal
blog now 😉
I have been browsing online more than 4 hours today,
yet I never found any interesting article like yours.
It’s pretty worth enough for me. In my view, if all webmasters and bloggers
made good content as you did, the internet will be much more useful than ever before.
Good info. Lucky me I discovered your blog by chance (stumbleupon).
I have book marked it for later!
We are a bunch 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 activity and our entire community will be thankful to you.
Undeniably imagine that which you said. Your favourite justification seemed to be on the internet
the easiest factor to bear in mind of. I say to you, I definitely get annoyed even as
other folks consider concerns that they plainly
do not recognize about. You managed to hit the nail upon the top and outlined out
the entire thing without having side effect , other people can take a signal.
Will probably be back to get more. Thank you
It’s amazing to pay a quick visit this website and
reading the views of all friends about this post, while
I am also keen of getting knowledge.
Admiring the commitment you put into your site and in depth information you present.
It’s great to come across a blog every once in a while that isn’t
the same outdated rehashed information. Excellent read! I’ve saved your
site and I’m adding your RSS feeds to my Google account.
A person essentially assist to make severely posts I
would state. That is the very first time I frequented your
website page and thus far? I amazed with the analysis you made to make
this actual post amazing. Wonderful process!
Hello There. I found your blog using msn. This is an extremely well written article.
I will be sure to bookmark it and come back to read more of your useful info.
Thanks for the post. I’ll certainly return. natalielise plenty of fish
Greetings! Very helpful advice in this particular article!
It is the little changes that will make the greatest changes.
Thanks for sharing!
If you are going for best contents like myself, simply go
to see this site every day since it offers quality
contents, thanks
An outstanding share! I’ve just forwarded this onto a co-worker who had been doing a little homework on this.
And he in fact ordered me lunch simply because I discovered it
for him… lol. So let me reword this…. Thanks for the meal!!
But yeah, thanx for spending time to discuss this
subject here on your blog.
This post provides clear idea for the new visitors of blogging, that truly how to do blogging and site-building.
Wow, amazing blog structure! How long have you been running a blog for?
you make blogging glance easy. The full look of your site is fantastic, as well as
the content material!
Ridiculous story there. What occurred after? Good luck! pof natalielise
An intriguing discussion is worth comment. I do believe that you ought to publish more about this subject matter, it might not be a taboo matter but typically people do not talk about these topics.
To the next! Best wishes!!
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 could do with a few pics to drive the message home
a little bit, but other than that, this is excellent blog.
A great read. I’ll definitely be back.
Hi there, I log on to your blog on a regular basis.
Your writing style is witty, keep up the good work!
Have you ever thought about adding a little bit more than just your articles?
I mean, what you say is valuable and everything.
Nevertheless imagine if you added some great pictures or
video clips to give your posts more, “pop”!
Your content is excellent but with pics and clips, this website could undeniably
be one of the very best in its field. Wonderful blog!
Asking questions are actually fastidious thing if you are not understanding
anything totally, however this piece of writing provides fastidious
understanding yet.
Hey! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any recommendations?
Magnificent items from you, man. I’ve be mindful your stuff previous
to and you’re simply too magnificent. I actually
like what you’ve acquired here, really like what you’re saying
and the best way through which you say it. You’re making
it entertaining and you continue to take care of to stay it
smart. I cant wait to read much more from you. That is really a great site.
Fantastic beat ! I would like to apprentice while you amend your web site, how could i subscribe for a blog web site?
The account aided me a acceptable deal. I had been tiny bit
acquainted of this your broadcast offered bright clear concept
I am really enjoying the theme/design of your website.
Do you ever run into any web browser compatibility issues?
A few of my blog audience have complained about my website not operating correctly in Explorer but looks great in Safari.
Do you have any tips to help fix this issue?
Very nice article, just what I wanted to find.
You actually make it seem so easy with your presentation but I find this matter to be really
something that I think I would never understand. It seems too complicated and extremely
broad for me. I’m looking forward for your next post, I’ll try to get the hang of it!
I was able to find good information from your blog articles.
This design is steller! You certainly know how to keep a reader amused.
Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Wonderful job.
I really loved what you had to say, and more than that, how you presented it.
Too cool!
Hi there, I want to subscribe for this blog to get most up-to-date updates, therefore where
can i do it please assist.
Hello! I’ve been following your blog 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 good job!
This text is priceless. Where can I find out more?
I used to be recommended this web site by way of my cousin. I’m now not positive whether this post is written by
way of him as nobody else realize such specific about my difficulty.
You’re wonderful! Thank you!
I blog frequently and I seriously thank you for your information. This great
article has truly peaked my interest. I’m going to take a note of
your site and keep checking for new information about once a week.
I opted in for your Feed as well.
I am really inspired with your writing abilities and also with the format on your blog.
Is that this a paid subject matter or did you modify it your self?
Either way stay up the excellent quality writing,
it is uncommon to peer a great blog like this one nowadays..
We’re a group of volunteers and opening a new scheme in our community.
Your web site offered us with valuable information to work
on. You’ve done a formidable job and our whole community will be grateful to you.
Unquestionably imagine that that you stated. Your favorite justification appeared to be on the internet the
simplest factor to consider of. I say to you, I certainly get irked whilst other folks consider issues that they just don’t know about.
You managed to hit the nail upon the highest as neatly as defined out the entire thing without having side-effects ,
other folks could take a signal. Will likely be again to get more.
Thanks
This post is invaluable. Where can I find out more?
I’m really impressed together with your writing skills and also
with the layout on your weblog. Is this a paid subject or did you modify it yourself?
Anyway keep up the nice high quality writing, it is rare to see a
great blog like this one today..
Hi i am kavin, its my first occasion to commenting anywhere, when i read
this article i thought i could also create comment due to this sensible article.
Hello, There’s no doubt that your website may be having browser compatibility issues.
Whenever I look at your blog in Safari, it looks fine however, if opening in Internet Explorer, it has some overlapping issues.
I simply wanted to give you a quick heads up! Besides that,
fantastic website!
What i don’t realize is in reality how you’re no longer really much more smartly-favored than you may
be now. You are very intelligent. You already know thus significantly in the case of this topic, made me individually believe it from
numerous varied angles. Its like women and men don’t seem to be interested except it is one thing to do with Lady gaga!
Your own stuffs nice. At all times handle
it up!
Hi there everyone, it’s my first go to see at this website,
and post is truly fruitful in favor of me, keep up posting these types
of articles or reviews.
Hello mates, how is the whole thing, and what you wish for to say on the
topic of this paragraph, in my view its truly remarkable in support
of me.
Thanks very interesting blog!
Hello! This is my first visit to your blog! We are a team of volunteers and starting a new
initiative in a community in the same niche.
Your blog provided us valuable information to work on. You have done a wonderful job!
I am really enjoying the theme/design of your site.
Do you ever run into any browser compatibility problems?
A number of my blog audience have complained about my blog not
operating correctly in Explorer but looks great in Opera.
Do you have any advice to help fix this issue?
Heya! I just wanted to ask if you ever have any trouble
with hackers? My last blog (wordpress) was hacked and
I ended up losing months of hard work due to no data backup.
Do you have any solutions to protect against hackers?
Thank you for any other informative web site.
The place else may I am getting that kind of information written in such an ideal method?
I have a challenge that I am just now working on, and I’ve been on the glance out for such info.
I seriously love your website.. Very nice colors & theme.
Did you make this website yourself? Please reply back as I’m looking to create my own blog and want to find out where you got this from or exactly what the theme is named.
Cheers!
You should be a part of a contest for one of the most useful sites on the net.
I will highly recommend this blog!
You ought to take part in a contest for one of the greatest blogs on the web.
I will recommend this web site!
I’ve been browsing online more than 4 hours today, yet I never found any interesting article
like yours. It’s pretty worth enough for me. In my opinion, if all website
owners and bloggers made good content as you did, the net will be a
lot more useful than ever before.
Wow that was odd. I just wrote an really long comment but after I clicked submit my comment didn’t show up.
Grrrr… well I’m not writing all that over again. Anyway, just wanted to say fantastic blog!
It’s an amazing article in support of all the internet people;
they will take benefit from it I am sure.
Generally I do not learn article on blogs, however I wish to say that this write-up very compelled me to take a look at and do it!
Your writing style has been surprised me. Thank you,
quite great article.
If some one needs expert view concerning
running a blog afterward i suggest him/her to pay a visit this blog, Keep up the pleasant work.
This website was… how do I say it? Relevant!! Finally I’ve found something that helped
me. Thanks a lot!
Hey very nice blog!
I really like what you guys are up too. This sort of clever
work and reporting! Keep up the awesome works guys I’ve included you
guys to my blogroll.
Very soon this website will be famous among all blogging visitors, due to it’s pleasant posts
It’s hard to find experienced people for this subject, however, you
sound like you know what you’re talking about!
Thanks
Hi to all, the contents existing at this web page are actually awesome for people experience, well, keep up the nice work fellows.
I really like it when individuals come together and share ideas.
Great site, continue the good work!
Have you ever thought about including a little bit more than just your articles? I mean, what you say is important and everything. However think about if you added some great visuals or video clips to give your posts more, “pop”! Your content is excellent but with pics and video clips, this website could certainly be one of the most beneficial in its niche. Terrific blog!
I constantly emailed this website post page to all my friends,
since if like to read it next my friends will too.
I don’t know whether it’s just me or if everybody else experiencing issues with your
blog. It seems like some of the text in your
posts are running off the screen. Can somebody else please provide feedback
and let me know if this is happening to them as well?
This might be a issue with my internet browser because I’ve had this happen previously.
Thanks
Hello, I enjoy reading all of your article post. I like to write a little comment to support you.
It is the best time to make some plans for the future and
it is time to be happy. I’ve read this submit and if I may I wish to suggest you few attention-grabbing things or
suggestions. Perhaps you could write subsequent articles referring to this article.
I wish to learn more issues approximately it!
It’s 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 wish to suggest you some interesting
things or tips. Perhaps you could write next articles referring to this article.
I wish to read more things about it!
What’s up i am kavin, its my first time to commenting anyplace,
when i read this article i thought i could also make comment due to this brilliant post.
Your style is unique in comparison to other people I’ve read stuff from.
Thanks for posting when you have the opportunity, Guess I will just bookmark this page.
I was suggested this website via my cousin. I am not sure whether or not this publish is written by him as nobody else know such special about my trouble.
You are wonderful! Thanks!
It’s appropriate time to make some plans for the future and it is
time to be happy. I’ve read this post and if I could I desire to suggest
you some interesting things or advice. Perhaps you could write next
articles referring to this article. I want to read even more things about it!
First of all I would like to say great blog! I had a quick question that I’d like to ask if you do not
mind. I was interested to know how you center yourself and clear your mind
before writing. I have had trouble clearing my thoughts
in getting my thoughts out there. I truly do take pleasure in writing however it just seems like the first 10 to 15 minutes are generally lost simply just trying to
figure out how to begin. Any suggestions or tips?
Thanks!
Very excellent info can be found on blog. “Education is what most receive, many pass on, and few possess.” by Karl Kraus.