题目大意
给定一棵$n(n \le 10^5)$个结点的树，每一个结点的特征值定义为这个结点的度
询问从根节点走到叶子结点的所有路径中本质不同的字符串的数量
解题报告
这题就是诸神眷顾的幻想乡的弱化版，撸一发广义SAM就可以了
不过GEOTCBRL考完之后给我们增加了一点姿势水平：
广义后缀自动机如果使用DFS建立的话，时间复杂度是$O($叶子结点深度和$)$的
如果使用BFS来建立的话，时间复杂度是$O(n \cdot$字符集大小$)$
这在15年刘研绎的集训队论文《后缀自动机在字典树上的拓展》中有详细的证明
其中还给出了构造极端数据的构造方法
所以这题字符集大小这么大的话，这样会T的
可能只有后缀数组才能做 QwQ
Code
这辣鸡代码是可以卡的，泥萌不要卡啊…….
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2000009;
int n,head[N],nxt[N],to[N],in[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 AddEdge(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;
}
class Suffix_Automaton{
int tot,len[N],fail[N],vis;
map<int,int> ch[N];
public:
inline Suffix_Automaton() {tot=1;}
inline int insert(int t, int c) {
if (ch[t]&&len[ch[t]]==len[t]+1) return ch[t];
int w = ++tot; len[w] = len[t] + 1;
for (;t&&!ch[t];t=fail[t]) ch[t] = w;
if (!t) fail[w] = 1;
else if (len[ch[t]] == len[t] + 1) fail[w] = ch[t];
else {
int nt = ++tot, pt = ch[t];
ch[nt] = ch[pt]; len[nt] = len[t] + 1;
fail[nt] = fail[pt]; fail[pt] = fail[w] = nt;
for (;t&&ch[t]==pt;t=fail[t]) ch[t] = nt;
} return w;
}
inline LL GetAns() {
LL ret = 0;
for (int i=2;i<=tot;i++)
ret += len[i] - len[fail[i]];
return ret;
}
}SAM;
void DFS(int w, int f, int ins) {
int nins = SAM.insert(ins, in[w]);
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
DFS(to[i], w, nins);
}
}
}
int main() {
n = read();
for (int i=1;i<n;i++) AddEdge(read(), read());
DFS(1, 1, 1);
printf("%lld\n",SAM.GetAns());
return 0;
}
you are in point of fact a excellent webmaster. The site
loading velocity is amazing. It sort of feels that you are doing any unique trick.
Furthermore, The contents are masterpiece. you’ve done a wonderful
task in this matter!
Thanks for finally writing about >【日常小测】Different Trips – Qizy’s Database <Liked it!
I am actually thankful to the owner of this site who has
shared this great piece of writing at at this time.
Hi there i am kavin, its my first occasion to commenting anyplace, when i read this paragraph i thought i could also create comment due to this brilliant post.
Excellent site. Lots of useful info here. I am sending it to several pals ans additionally
sharing in delicious. And naturally, thank you in your effort!
I constantly emailed this blog post page to all my associates,
for the reason that if like to read it afterward my links
will too.
First of all I want to say superb blog! I had a quick question that I’d like to ask
if you don’t mind. I was curious to know how you
center yourself and clear your mind before writing.
I have had difficulty clearing my thoughts in getting
my ideas out there. I truly do enjoy writing but it just seems
like the first 10 to 15 minutes are lost simply just trying to figure out how to begin. Any suggestions
or hints? Kudos!
First off I want to say excellent blog! I had a quick question in which I’d like to ask if you
do not mind. I was interested to know how
you center yourself and clear your head before writing.
I’ve had a tough time clearing my mind in getting
my ideas out there. I do enjoy writing however it just seems like the first 10 to
15 minutes are lost just trying to figure
out how to begin. Any ideas or hints? Cheers!
Hello, I log on to your new stuff regularly.
Your humoristic style is witty, keep doing
what you’re doing!
It’s an remarkable piece of writing for all the
web users; they will take benefit from it I am sure.
Excellent weblog here! Additionally your website lots up very fast!
What host are you the use of? Can I get your affiliate link on your host?
I wish my web site loaded up as fast as yours lol
I have been exploring for a little for any high quality articles or blog posts on this
kind of house . Exploring in Yahoo I finally stumbled upon this
site. Reading this information So i am happy to express that
I’ve an incredibly just right uncanny feeling I found out just what I needed.
I most no doubt will make certain to don?t fail to remember this site and give
it a look regularly.
I love your blog.. very nice colors & theme. Did you create this website yourself or did you
hire someone to do it for you? Plz answer back as I’m looking to construct my own blog and would like to know where u got
this from. thank you
It’s not my first time to pay a visit this web site, i
am browsing this website dailly and obtain nice facts from here every day.
Hello there! I simply wish to offer you a big thumbs up
for your great info you have right here on this post.
I’ll be coming back to your website for more soon.
It’s very easy to find out any topic on web as compared to textbooks, as I found this paragraph at this web page.
Hey there just wanted to give you a quick heads up
and let you know a few of the pictures aren’t loading
correctly. I’m not sure why but I think its a linking issue.
I’ve tried it in two different internet browsers and both show the same outcome.
natalielise pof
Thank you for the auspicious writeup. It if truth be told was a leisure account it.
Glance complicated to more brought agreeable from you!
By the way, how could we keep up a correspondence?
I think that is one of the most vital information for me.
And i am satisfied studying your article. However wanna observation on few
basic things, The website style is perfect, the articles is actually excellent :
D. Just right activity, cheers
Thanks for any other great post. The place else may just anybody
get that kind of info in such a perfect method of writing?
I’ve a presentation next week, and I am at the look for such info.
Pretty section of content. I just stumbled upon your web site and in accession capital to assert that I acquire
actually enjoyed account your blog posts. Any way I
will be subscribing to your augment and even I achievement you access consistently rapidly.
I am genuinely delighted to glance at this web site posts which contains plenty of
valuable facts, thanks for providing these kinds of data.
If you want to increase your familiarity simply keep visiting this site and be updated with the
hottest information posted here.
Great information. Lucky me I found your website by chance
(stumbleupon). I’ve saved as a favorite for later!
Hello there! I know this is kind of off topic
but I was wondering if you knew where I could get a captcha
plugin for my comment form? I’m using the same blog platform
as yours and I’m having trouble finding one?
Thanks a lot!
Hello, i think that i saw you visited my web
site thus i came to “return the favor”.I’m attempting
to find things to enhance my web site!I suppose its ok to use some of your
ideas!!
Howdy! Someone in my Facebook group shared this site with us so I came to take a look.
I’m definitely enjoying the information. I’m book-marking and will
be tweeting this to my followers! Wonderful blog and outstanding design.
Wow! This blog looks just like my old one! It’s on a totally different topic but it has pretty much the same page layout and design. Superb choice of
colors!
Hey There. I discovered your blog using msn. That is a really smartly written article.
I’ll be sure to bookmark it and come back to learn more
of your useful info. Thank you for the post. I’ll certainly comeback.
What a data of un-ambiguity and preserveness of precious
knowledge about unexpected feelings.
Hi! I know this is somewhat off topic but I was wondering which
blog platform are you using for this website? I’m getting sick and
tired of WordPress because I’ve had problems with hackers and I’m looking at options for another platform.
I would be fantastic if you could point
me in the direction of a good platform.
Thanks to my father who informed me about this weblog,
this website is genuinely remarkable.
Wow, incredible weblog layout! How lengthy have you been blogging
for? you make blogging glance easy. The entire look of your site is magnificent,
let alone the content!
Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your webpage?
My blog is in the exact same area of interest as yours and my visitors would certainly benefit from a lot of the information you present here.
Please let me know if this okay with you. Regards!
Excellent beat ! I wish to apprentice while you amend
your site, how can i subscribe for a blog web site? The account helped me
a acceptable deal. I had been a little bit acquainted of
this your broadcast provided bright clear idea
Fantastic web site. Lots of helpful information here. I am sending it to some pals ans also sharing in delicious.
And certainly, thanks for your sweat!
When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get several emails with the same comment.
Is there any way you can remove people from that service?
Thanks a lot!
Thanks for ones marvelous posting! I truly enjoyed reading it, you might be a great author.I will make
certain to bookmark your blog and will come back later on. I want to encourage you continue your great posts, have a nice day!
Greetings I am so delighted I found your webpage, I really found you by mistake, while I
was browsing on Bing for something else, Nonetheless I am here now and would
just like to say many thanks for a fantastic post and a all round thrilling blog
(I also love the theme/design), I don’t have time to read it all at
the moment but I have book-marked it and also added your RSS feeds,
so when I have time I will be back to read a lot more, Please
do keep up the superb work.
It is the best 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 few interesting things or advice.
Perhaps you could write next articles referring to this article.
I wish to read even more things about it!
I’m amazed, I have to admit. Seldom do I encounter a blog that’s both equally educative and interesting, and let me tell
you, you’ve hit the nail on the head. The problem is something not enough
people are speaking intelligently about. I’m very happy that
I found this during my search for something relating
to this.
Hey I am so excited I found your web site, I really found
you by error, while I was researching on Yahoo for something else, Regardless I am here
now and would just like to say thanks for a incredible post and a all round enjoyable
blog (I also love the theme/design), I don’t have time to
look over it all at the moment but I have bookmarked it and also included your RSS
feeds, so when I have time I will be back to
read more, Please do keep up the fantastic work.
Excellent web site you have got here.. It’s hard to find
good quality writing like yours nowadays. I really appreciate individuals like you!
Take care!!
I just could not go away your web site before suggesting that I actually
loved the standard info an individual provide to your guests?
Is gonna be back regularly to check out new posts
Thanks for one’s marvelous posting! I really enjoyed reading it, you are a great author.I will make sure to bookmark your blog and will come back in the foreseeable future.
I want to encourage you to ultimately continue your great job, have a nice holiday weekend!
Hello, Neat post. There is a problem together
with your site in internet explorer, would check this?
IE still is the marketplace chief and a large component to people will leave
out your fantastic writing because of this problem.
Hello everyone, it’s my first go to see at this website, and piece of writing is truly fruitful designed for
me, keep up posting these types of content.
It’s awesome in support of me to have a website, which is beneficial for my
experience. thanks admin
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 me from that service?
Thank you!
My partner and I stumbled over here coming from a different web
page and thought I might check things out. I like what I see so now i am following you.
Look forward to checking out your web page again.
Wow that was odd. I just wrote an incredibly long
comment but after I clicked submit my comment didn’t appear.
Grrrr… well I’m not writing all that over again. Regardless, just wanted to say superb blog!
Hi there to all, the contents existing at this website are in fact
amazing for people knowledge, well, keep up the nice work
fellows.
Wonderful goods from you, man. I have be aware your stuff prior to and you’re simply extremely excellent.
I actually like what you’ve received right here,
really like what you are stating and the best way by which you say it.
You are making it entertaining and you continue to take care
of to keep it sensible. I can’t wait to read much more from you.
This is actually a wonderful website.
Hello there, just became aware of your blog through Google, and found that it is really informative.
I am going to watch out for brussels. I will be grateful
if you continue this in future. Lots of people will be benefited from your writing.
Cheers!
Thank you for every other fantastic post. The place else could anybody get
that type of info in such an ideal way of writing? I’ve a presentation next
week, and I’m on the look for such info.
Do you have a spam problem on this site; I also am a blogger, and I was wanting to know your situation;
we have created some nice practices and we are looking
to swap solutions with others, why not shoot me an e-mail if interested.
Pretty section of content. I just stumbled upon your site and in accession capital to say that I acquire in fact loved account your weblog posts.
Any way I will be subscribing for your augment and even I fulfillment you get right of entry to persistently quickly.
I don’t even know how I ended up here, but I thought this post was great.
I do not know who you are but definitely you’re going to a famous blogger if
you aren’t already 😉 Cheers!
I constantly emailed this website post page to all my
contacts, because if like to read it then my links will too.
Hello, I think your website might be having browser compatibility issues.
When I look at your website in Opera, it looks fine but when opening in Internet Explorer, it has
some overlapping. I just wanted to give you a quick heads up!
Other then that, excellent blog!
This is a good tip especially to those fresh to the blogosphere.
Short but very precise information… Many thanks for sharing this one.
A must read post!
We are a gaggle of volunteers and opening a new
scheme in our community. Your web site provided us with useful
info to work on. You’ve done a formidable job and our entire neighborhood might be thankful to you.
Hi, I do think this is an excellent web site. I stumbledupon it 😉 I am going to come
back yet again since I book marked it. Money and freedom is the best way to change, may you be rich and continue to help other people.
Write more, thats all I have to say. Literally, it seems as
though you relied on the video to make your point.
You obviously know what youre talking about, why waste your intelligence on just
posting videos to your site when you could be giving us something enlightening to read?
Hi there, I found your web site by way of Google while looking for a similar matter, your site came up, it appears
good. I have bookmarked it in my google bookmarks.
Hi there, simply become alert to your weblog thru Google, and found that it’s truly informative.
I am gonna watch out for brussels. I will appreciate in case you continue this in future.
Many other people will probably be benefited from your writing.
Cheers!
Amazing! Its genuinely awesome piece of writing, I have got much
clear idea concerning from this article.
Magnificent goods from you, man. I’ve remember your stuff previous to and
you are just too magnificent. I actually like what you have
bought here, certainly like what you’re stating and the way through which you say it.
You’re making it entertaining and you still take care of to
stay it wise. I cant wait to learn much more from you.
This is actually a great site.
Today, while I was at work, my cousin stole my iPad and tested to see if it can survive
a 30 foot drop, just so she can be a youtube sensation. My iPad is now broken and
she has 83 views. I know this is entirely off topic but I had to share it with someone!
This design is incredible! You most 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!) Fantastic job. I really enjoyed what you had to say, and more than that, how you presented it.
Too cool!
An outstanding share! I’ve just forwarded this
onto a colleague who was doing a little research on this.
And he actually ordered me breakfast simply because I stumbled upon it for him…
lol. So let me reword this…. Thank YOU for the meal!!
But yeah, thanx for spending the time to talk about this subject here on your blog.
Hurrah, that’s what I was exploring for, what a data! existing here at this website, thanks admin of this web
site.
This post gives clear idea in support of the new viewers of blogging, that truly how to do blogging.
Thanks for helping out, great information.
Nice replies in return of this question with real arguments
and explaining all on the topic of that.
Simply want to say your article is as surprising. The clarity in your post is simply great and i could assume you’re an expert on this subject. Well with your permission allow me to grab your feed to keep updated with forthcoming post. Thanks a million and please carry on the gratifying work.
Thanks for another informative site. Where else may I am getting that kind of
information written in such an ideal approach?
I have a mission that I am just now operating on, and I’ve been on the look out
for such information.
Excellent article! We will be linking to this great content on our
site. Keep up the great writing.
I think this is among the most vital information for
me. And i am glad reading your article. But should remark on few general things, The web site
style is great, the articles is really great : D.
Good job, cheers
Your style is so unique compared to other people I
have read stuff from. Thanks for posting when you’ve got the opportunity, Guess I will just bookmark this page.
We stumbled over here different web page and thought I should check things out.
I like what I see so now i’m following you. Look forward to exploring your web page yet again.
I like the valuable information you supply on your articles.
I will bookmark your weblog and test again right here regularly.
I’m slightly certain I will be informed many new stuff right
right here! Good luck for the following!
Hi! 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 back up. Do you have any solutions to protect against hackers?
Thanks a bunch for sharing this with all of us you
really recognize what you’re speaking about!
Bookmarked. Please also consult with my web site =). We could have a link change arrangement among us
My family every time say that I am killing my time here
at web, but I know I am getting familiarity all the time by reading such nice content.
Hello! Would you mind if I share your blog with my twitter group?
There’s a lot of folks that I think would really appreciate
your content. Please let me know. Cheers
Hi there would you mind sharing which blog platform
you’re working with? 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 unique. P.S My apologies for getting off-topic but I had to ask!
I got good info from your blog