相关链接
题目传送门：http://codeforces.com/problemset/problem/715/C
官方题解：http://codeforces.com/blog/entry/47169
解题报告
要求统计树上路径，那么基本上确定是DP或者树分治了
想一想，好像DP的状态不好表示的样子，于是就直接点分治啦！
考虑对于每一个中心，统计经过该点符合要求的路径数
很明显需要将路径剖成两半，一半扔到map里，另一半直接查
但这题还有需要注意的就是如何去掉两段都在同一子树的非法情况
似乎直接像之前一样在子树的根部调用cal()直接剪掉的方法不管用了
于是可以先DFS一遍，统计所有信息
然后再处理每一个子树的时候，先DFS一遍，把该子树的信息给去掉
查询完成之后，再DFS一遍把信息给加回去
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200000 + 9;
int head[N],nxt[N],cost[N],to[N],REV[N];
int n,MOD; LL vout;
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, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}
void gcd(int a, LL &x, int b, LL &y) {
if (!b) {x = 1, y = 0;}
else {gcd(b,y,a%b,x);y-=a/b*x;}
}
inline int gcd(int a, int b) {
static LL x,y;
gcd(a,x,b,y);
return (x % MOD + MOD) % MOD;
}
namespace Node_Decomposition{
#define ND Node_Decomposition
const int INF = 1e9;
int tot,node_sz,root,cur;
int sum[N],dep[N],vis[N];
map<int,int> cnt;
void Get_Root(int w, int f) {
sum[w] = 1; int mx = 0;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, node_sz - sum[w]);
if (mx < cur) cur = mx, root = w;
}
void DFS(int w, int f, int delta, LL p, int val) {
cnt[val] += delta;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]] && to[i] != f) {
DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
}
}
}
void cal(int w, int f, int t, LL val) {
vout += cnt[(-val*REV[t]%MOD+MOD)%MOD];
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]] && to[i] != f) {
cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
}
}
}
void solve(int w, int sz) {
vis[w] = 1; cnt.clear();
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
vout += cnt[0]; cnt[0]++;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
cal(to[i], w, 1, cost[i] % MOD);
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
cur = INF; Get_Root(to[i], w);
solve(root, node_sz);
}
}
}
inline void solve() {
cur = INF; node_sz = n;
Get_Root(1,1);
solve(root,n);
}
};
int main() {
n = read(); MOD = read();
for (int i=1,u,v,w;i<n;i++) {
u = read(); v = read(); w = read();
Add_Edge(u + 1, v + 1, w);
}
REV[0] = 1; REV[1] = gcd(10, MOD);
for (int i=2;i<=n;i++)
REV[i] = (LL)REV[i-1] * REV[1] % MOD;
ND::solve();
printf("%lld\n",vout);
return 0;
}
Attractive section of content. I just stumbled upon your weblog and in accession capital
to assert that I acquire in fact enjoyed account your blog
posts. Any way I will be subscribing to your augment
and even I achievement you access consistently fast.
Hi there! Quick question that’s totally 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 theme or plugin that might be able to correct this problem.
If you have any recommendations, please share. Thanks!
Hi! I just want to give you a huge thumbs up for the great information you have got here on this post.
I will be coming back to your blog for more soon.
Your method of explaining the whole thing in this paragraph is
actually good, all can easily know it, Thanks a lot.
Hello there, I found your blog by way of Google while
searching for a comparable matter, your web site came up, it seems to
be good. I have bookmarked it in my google bookmarks.
Hello there, just changed into aware of your blog
via Google, and located that it is truly informative. I
am going to watch out for brussels. I’ll appreciate if
you happen to proceed this in future. Numerous other folks shall be benefited out of
your writing. Cheers!
Hello there, I discovered your site by way of Google even as looking for a related matter, your web site got here up,
it appears great. I have bookmarked it in my google bookmarks.
Hi there, simply changed into alert to your weblog via Google,
and found that it’s really informative. I am going to be careful for brussels.
I’ll appreciate should you continue this in future.
A lot of other folks might be benefited from your
writing. Cheers!
Spot on with this write-up, I honestly believe that this web
site needs a great deal more attention. I’ll probably be
back again to read through more, thanks for the advice!
Excellent blog you have here.. It’s hard to find high quality writing
like yours these days. I honestly appreciate people like you!
Take care!!
Ridiculous quest there. What happened after?
Take care!
Good answers in return of this question with real arguments
and explaining everything on the topic of that.
you’re in reality a just right webmaster. The web site loading velocity is incredible.
It seems that you are doing any unique trick. In addition, The contents are masterpiece.
you’ve done a excellent task in this matter!
WOW just what I was looking for. Came here by searching for gamefly free trial
Sweet blog! I found it while browsing on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Thank you
Hello everyone, it’s my first pay a quick visit at this site,
and post is genuinely fruitful designed for me, keep up posting such posts.
all the time i used to read smaller posts that also clear their motive, and
that is also happening with this paragraph which I am reading here.
Excellent article. Keep writing such kind of info on your site.
Im really impressed by it.
Hey there, You’ve performed an incredible job.
I’ll certainly digg it and individually suggest
to my friends. I am sure they’ll be benefited from this web site.
This paragraph gives clear idea in favor of the new viewers of blogging,
that in fact how to do running a blog.
Hi there would you mind sharing which blog platform you’re working with?
I’m planning to start my own blog in the near future but I’m having a difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most blogs and
I’m looking for something completely unique.
P.S My apologies for being off-topic but I had to ask!
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 extraordinary job!
Do you mind if I quote a few of your posts as long as I
provide credit and sources back to your site?
My blog is in the very same area of interest as yours
and my users would genuinely benefit from some
of the information you present here. Please let me know if this okay with you.
Thanks!
Hi there I am so thrilled I found your website, I really found
you by error, while I was searching on Bing for something else,
Nonetheless I am here now and would just like to say thanks for a marvelous 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 book-marked it and also added your RSS feeds, so when I have time I will be back to read much more, Please do keep up
the excellent jo.
It’s hard to find well-informed people on this subject, but you
seem like you know what you’re talking about! Thanks
Unquestionably believe that which you said. Your favorite justification seemed to
be on the web the easiest thing to be aware of.
I say to you, I certainly get irked while people think about worries that they
plainly do not know about. You managed to hit the nail upon the top and
also defined out the whole thing without having side-effects , people
could take a signal. Will probably be back to get more.
Thanks
Hi, i think that i saw you visited my website thus i came to “return the
favor”.I’m attempting to find things to enhance my site!I suppose its ok to
use some of your ideas!!
This page definitely has all of the info I needed about this subject and didn’t know who to ask.
It’s in reality a nice and useful piece of info.
I’m satisfied that you shared this useful information with
us. Please stay us informed like this. Thank you for sharing.
Hi my loved one! I want to say that this article is awesome, great written and come with almost all
important infos. I would like to see extra posts like this
.
I do accept as true with all of the ideas you have introduced for your post.
They are very convincing and can definitely work.
Still, the posts are too short for beginners. May you
please extend them a bit from next time? Thanks for the post.
Good article. I am dealing with a few of these issues as well..
Thanks for another wonderful post. Where else could anybody get that
kind of info in such an ideal method of writing? I have a presentation next week, and I’m at the
look for such info.
What’s up mates, how is all, and what you desire to say on the topic
of this article, in my view its truly amazing designed for me.
plenty of fish natalielise
This is my first time pay a visit at here and i am really impressed to read all
at one place.
This is a topic that is close to my heart… Cheers!
Exactly where are your contact details though?
obviously like your web site but you need to take a look at
the spelling on quite a few of your posts. Many of them are rife with spelling problems and I find
it very troublesome to inform the reality on the other hand I will certainly come back
again.
Fantastic goods from you, man. I’ve understand your stuff previous
to and you’re just too excellent. I actually like what you have
acquired here, really like what you’re stating and the way in which you say
it. You make it entertaining and you still care for to keep it wise.
I can’t wait to read far more from you. This is
really a tremendous web site.
Wonderful blog! I found it while searching on Yahoo News. Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Cheers
I used to be able to find good advice from your blog posts.
You actually make it appear really easy along with your presentation but I in finding this matter to be really
one thing that I feel I might by no means understand.
It sort of feels too complicated and very huge for me.
I’m having a look ahead in your next publish, I will try to get
the hang of it!
Amazing! Its actually remarkable article, I have got much clear idea on the
topic of from this article. natalielise plenty of fish
Howdy! I could have sworn I’ve been to this web site before but after browsing through some of the posts I realized it’s new to me. Anyways, I’m certainly happy I found it and I’ll be bookmarking it and checking back frequently!
Have you ever considered about including a little bit more than just your articles?
I mean, what you say is fundamental and all.
However think about if you added some great pictures or videos to give your posts more, “pop”!
Your content is excellent but with pics and videos, this website could undeniably be one of the greatest in its niche.
Good blog!
Great web site. A lot of helpful information here. I am sending it to several buddies ans additionally sharing in delicious.
And naturally, thank you on your effort!
Hello everyone, it’s my first visit at this site, and piece of writing is genuinely fruitful for me, keep up posting
such content.
Valuable info. Lucky me I found your web site unintentionally,
and I’m stunned why this accident did not took place in advance!
I bookmarked it.
Howdy! Someone in my Facebook group shared this site
with us so I came to look it over. I’m definitely enjoying the information.
I’m book-marking and will be tweeting this to my followers!
Terrific blog and excellent design and style.
I know this site gives quality based articles and extra
stuff, is there any other website which
gives these things in quality?
Greetings I am so grateful I found your web site, I really found
you by accident, while I was looking on Digg for something else, Anyways
I am here now and would just like to say thanks for a tremendous post and a all round exciting blog (I
also love the theme/design), I don’t have time to read
through it all at the moment but I have bookmarked it and
also added your RSS feeds, so when I have time I will
be back to read much more, Please do keep up the awesome jo.
After looking into a few of the blog posts on your website,
I truly like your way of writing a blog. I book-marked it to my bookmark
site list and will be checking back in the near future.
Please check out my web site as well and tell me how
you feel.
Incredible! This blog looks exactly like my old one! It’s on a totally different subject
but it has pretty much the same layout and design. Great choice of colors!
It’s really very complicated in this busy life to listen news on TV, therefore I just use
world wide web for that reason, and get the newest
news.
I’m pretty pleased to uncover this great site. I wanted to thank you for your time due to this fantastic read!!
I definitely savored every little bit of it and i also have you saved to fav to
look at new things in your blog.
Yes! Finally someone writes about minecraft games.
Hey there! This is my first comment here so I
just wanted to give a quick shout out and say
I truly enjoy reading through your posts. Can you recommend any other blogs/websites/forums that deal with the same subjects?
Appreciate it!
Piece of writing writing is also a excitement, if you be familiar with afterward you can write or else it is complicated to write.
Hey 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 information. Thanks for the
post. I’ll certainly return.
If you would like to get a great deal from this piece of writing then you have to apply such strategies to your won website.
I am regular visitor, how are you everybody? This
post posted at this website is genuinely nice.
I was able to find good information from your blog posts.
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! However, how can we communicate?
Wonderful blog! Do you have any tips and hints for aspiring writers?
I’m hoping to start my own site 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 options out there that I’m totally overwhelmed ..
Any tips? Bless you!
Thanks for a marvelous posting! I definitely enjoyed reading
it, you could be a great author. I will be sure to bookmark your blog and will come back later in life.
I want to encourage continue your great work, have a nice holiday
weekend!
I was able to find good information from your articles.
An interesting discussion is worth comment. I believe that you ought to publish more on this issue, it may not be a taboo subject but usually people don’t talk about
such issues. To the next! Best wishes!!
It is not my first time to visit this web page, i am browsing this website dailly and obtain pleasant facts
from here every day.
I am actually grateful to the holder of this web page who has
shared this great article at at this time.
Attractive section of content. I just stumbled upon your web site and in accession capital
to assert that I acquire in fact enjoyed account your
blog posts. Anyway I’ll be subscribing to your feeds and even I achievement you access consistently fast.
Nice blog here! Also your web site loads up fast!
What web host are you using? Can I get your affiliate link to your host?
I wish my site loaded up as fast as yours lol
I read this article completely on the topic of the difference of hottest and preceding technologies, it’s remarkable article.
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.
If you want to take a great deal from this article
then you have to apply these strategies to
your won weblog.
Woah! I’m really digging the template/theme of this blog.
It’s simple, yet effective. A lot of times it’s very hard to get that
“perfect balance” between user friendliness and appearance.
I must say you have done a very good job with this. In addition, the
blog loads super fast for me on Firefox. Excellent Blog!
It’s difficult to find well-informed people about this topic,
however, you seem like you know what you’re talking about!
Thanks
After going over a number of the blog articles on your site, I truly like your
way of writing a blog. I saved it to my bookmark webpage list
and will be checking back in the near future. Take a look at my website as well and tell me your
opinion.
Link exchange is nothing else except it is just placing the other person’s
website link on your page at proper place and other person will also do similar in support of you.
Thanks for a marvelous posting! I certainly enjoyed reading it, you can be
a great author.I will always bookmark your blog and may
come back sometime soon. I want to encourage continue your great writing, have a nice afternoon!
Wonderful, what a webpage it is! This blog gives valuable facts to us,
keep it up.
Hi there! This is my 1st comment here so I just wanted to give a
quick shout out and tell you I really enjoy reading through your posts.
Can you recommend any other blogs/websites/forums that cover the same topics?
Thanks a lot!
My relatives all the time say that I am killing my time here at
web, however I know I am getting experience daily by reading such fastidious articles.
Very good post! We will be linking to this particularly great
content on our site. Keep up the good writing.
Hello my friend! I want to say that this
article is amazing, great written and come with almost
all significant infos. I’d like to look extra posts like this .
Thanks , I’ve just been searching for information approximately this topic for a
long time and yours is the best I have came upon till
now. However, what about the bottom line?
Are you positive about the supply?
Thanks for sharing such a good opinion, paragraph is
pleasant, thats why i have read it entirely
Why viewers still make use of to read news papers when in this technological globe the whole thing
is presented on net?
Hello, I think your blog might be having browser
compatibility issues. When I look at your blog in Safari, 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, terrific blog!
My partner and I absolutely love your blog and find the majority of
your post’s to be exactly what I’m looking for.
Would you offer guest writers to write content for you?
I wouldn’t mind composing a post or elaborating on a lot of the subjects
you write related to here. Again, awesome website!
Attractive component of content. I just stumbled upon your
web site and in accession capital to assert that
I get actually loved account your weblog posts.
Any way I will be subscribing to your feeds and even I achievement you get admission to constantly rapidly.
Thank you for the good writeup. It in fact was a amusement account
it. Look advanced to more added agreeable from you! By the way, how can we communicate?
Hi there, I log on to your blog regularly.
Your humoristic style is witty, keep it up!
Hello Dear, are you actually visiting this website regularly, if so after that you will
without doubt obtain nice knowledge.
Hi my friend! I want to say that this article is amazing, great written and come with almost all vital infos. I’d like to look extra posts like this.
I am sure this paragraph has touched all the internet viewers,
its really really fastidious paragraph on building up new blog.
Oh my goodness! Impressive article dude! Thank you, However I am encountering issues with your RSS. I don’t know why I am unable to join it. Is there anybody having identical RSS problems? Anyone that knows the solution can you kindly respond? Thanks!!
You’ve made some good points there. I looked on the net for more info about the issue and found most people will go along with your views on this website.
Yes! Finally someone writes about plenty of fish vs match.com free trial.
I was able to find good information from your blog posts.
Thanks for your marvelous posting! I genuinely enjoyed reading
it, you can be a great author.I will always bookmark your blog
and definitely will come back at some point.
I want to encourage continue your great writing, have a nice weekend!
Ahaa, its fastidious discussion about this paragraph here at this blog,
I have read all that, so at this time me also commenting here.
Hello, I log on to your new stuff daily. Your story-telling style is witty, keep it up!
What’s up, its nice article regarding media print, we all know media is a fantastic source of facts.
For most recent information you have to visit world-wide-web and on internet I found this website as a best site for hottest updates.
I’m not sure where you are getting your info, but good topic.
I needs to spend some time learning much more or understanding more.
Thanks for great info I was looking for this info for my mission.
Hey! This post couldn’t 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 page to him. Fairly certain he will have a good read.
Thanks for sharing!
Hi there Dear, are you genuinely visiting this web site regularly, if so then you will without doubt
take good know-how.
Hey There. I found your blog using msn. This is a very well written article.
I’ll make sure to bookmark it and return to read more of your
useful info. Thanks for the post. I’ll certainly return.
Thanks for sharing such a nice thinking,
paragraph is fastidious, thats why i have read it entirely
A round of applause for your blog post.Thanks Again. Much obliged.
I cannot thank you enough for the blog article.Really thank you! Cool.
Say, you got a nice blog post.Thanks Again. Much obliged.
Wow, great article.Really looking forward to read more. Really Great.
Howdy! I simply want to offer you a huge thumbs up
for your excellent information you have right here on this post.
I am returning to your site for more soon.
Hey, thanks for the blog.
Great, thanks for sharing this blog post.Really looking forward to read more. Keep writing.
Awesome article.Thanks Again. Will read on…
Muchos Gracias for your article post. Will read on…
Thanks again for the blog.Much thanks again. Keep writing.
Thanks again for the blog article.Really thank you! Want more.
I think this is a real great blog.Really thank you! Really Cool.
Thanks again for the blog post.Thanks Again. Awesome.
Major thankies for the blog.Really thank you! Awesome.
Say, you got a nice article.Really thank you! Keep writing.
Thanks for the blog post.Really looking forward to read more. Really Great.
Major thanks for the blog article.Really looking forward to read more. Great.
Great, thanks for sharing this article post.Thanks Again. Will read on…
Great blog post.Really looking forward to read more. Keep writing.
Im thankful for the post.Really looking forward to read more. Want more.
Really enjoyed this blog.Thanks Again. Really Cool.
Interesting blog! Is your theme custom made or did you download it from somewhere? A design like yours with a few simple adjustements would really make my blog shine. Please let me know where you got your design. Many thanks
Im grateful for the article.Much thanks again. Really Great.
I cannot thank you enough for the blog post.Really thank you! Awesome.
I really liked your article post.Really thank you! Cool.
Thanks so much for the blog article.Really looking forward to read more. Cool.
I really enjoy the blog.Really thank you! Want more.
Very good article post.Much thanks again.
Thank you ever so for you blog post.Really looking forward to read more. Great.
I value the blog post.Much thanks again. Much obliged.
Wow, great article post.Much thanks again. Much obliged.
Very informative article post.Thanks Again. Will read on…
Thanks again for the blog post.Really looking forward to read more. Really Great.
I cannot thank you enough for the article.Much thanks again. Cool.
A round of applause for your post.Thanks Again. Much obliged.
I loved your article post.Really looking forward to read more. Really Cool.
I really enjoy the blog.Much thanks again. Really Great.
Thanks again for the blog article.Thanks Again. Awesome.
Looking forward to reading more. Great blog article.Really thank you! Great.
This is one awesome post. Really Cool.
Wow, great article post.Really looking forward to read more. Fantastic.
This is one awesome article.Really thank you! Cool.
Very good post. Fantastic.
Really informative blog post.Thanks Again. Cool.
Thanks for the blog.Really looking forward to read more. Great.
Im obliged for the post.Really thank you! Keep writing.
I cannot thank you enough for the article.Much thanks again. Great.
Enjoyed every bit of your post.Thanks Again. Much obliged.
I loved your blog. Will read on…
I appreciate you sharing this article.Really thank you! Awesome.
Major thanks for the blog.
I value the article post.Really thank you! Really Great.
Thank you ever so for you blog. Want more.
Thanks for the article.Really thank you! Really Great.
I value the blog article.Thanks Again. Awesome.
I appreciate you sharing this article post.Thanks Again. Much obliged.
Very informative blog.Thanks Again. Great.
Major thanks for the article post.Really thank you!
Thanks again for the blog post.Much thanks again. Want more.
Really enjoyed this post.Much thanks again. Fantastic.
Your quite own commitment to receiving the message throughout arrived to be rather effective and have consistently empowered employees just like us to attain their desired aims.
Enjoyed every bit of your blog article.Really looking forward to read more. Awesome.
Thanks-a-mundo for the post.Really thank you! Much obliged.
Very neat post. Will read on…
Present without the answers to be able to the difficulties you’ve fixed out through this guideline is a critical situation, as well as typically the kind which could possess badly affected my whole career if I experienced not discovered your site.
Im obliged for the blog post.Much thanks again.
오피 사이트 You’re more helpful than you realize.