相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1468
主定理相关：http://raytaylorlin.com/Tech/algorithm/master-method/
神犇题解：http://www.cnblogs.com/iwtwiioi/p/4172279.html
题解
就是点分治的模板题啊!
另外关于主定理的话，我觉得这个式子说得很清楚：
若 $T(n) \le aT({n \over b}) + O({n^d})$
则 \(T(n) = \begin{cases} O(n^d \log n) & a = {b^d} \cr O(n^d) & a < {b^d} \cr O({n^{ { {\log }_b }a } }) & a > {b^d} \end{cases}\)
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 40000 + 9;
const int M = N << 1;
const int INF = 10000000;
int head[N],nxt[M],to[M],cost[M],vis[N],dep[N],sum[N];
int n,k,tot,cur,num_node,root,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 Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
mx = max(mx, sum[to[i]]);
sum[w] += sum[to[i]];
}
}
mx = max(mx, num_node - mx);
if (mx < cur) {
root = w;
cur = mx;
}
}
void Get_Dep(int w, int f, int bas) {
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && !vis[to[i]]) {
dep[++tot] = bas + cost[i];
Get_Dep(to[i], w, dep[tot]);
}
}
}
inline int cal(int w, int bas) {
dep[tot=1] = bas;
Get_Dep(w, w, bas);
sort(dep+1, dep+1+tot);
int r = tot, l = 1, ret = 0;
while (l < r) {
while (l < r && dep[l] + dep[r] > k) r--;
ret += r - l++;
}
return ret;
}
void solve(int w, int sz) {
vis[w] = 1;
vout += cal(w, 0);
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
vout -= cal(to[i], cost[i]);
num_node = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
cur = INF; Get_Root(to[i], w);
solve(root, num_node);
}
}
}
int main() {
n = read();
for (int i=1,u,v,w;i<n;i++) {
u = read(); v = read(); w = read();
Add_Edge(u, v, w);
}
k = read();
num_node = n; cur = INF; Get_Root(1, 1);
solve(root, n);
printf("%d",vout);
return 0;
}
楼下是疯子。哈哈
Howdy very nice website!! Man .. Excellent .. Superb ..
I’ll bookmark your site and take the feeds also? I’m happy
to seek out numerous useful info right here within the
publish, we’d like develop more techniques on this regard, thank you for
sharing. . . . . .
What’s up everybody, here every one is sharing these know-how, thus it’s
nice to read this website, and I used to pay a quick visit this weblog daily.
Everything is very open with a really clear description of
the issues. It was truly informative. Your website is very
helpful. Thanks for sharing!
Hi would you mind sharing which blog platform you’re working with?
I’m planning to start my own blog soon but I’m having a
tough time choosing 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 unique.
P.S Apologies for getting off-topic but I had to ask!
Thanks for ones marvelous posting! I quite enjoyed reading
it, you could be a great author. I will remember to bookmark
your blog and will come back in the foreseeable
future. I want to encourage you continue your great writing, have a nice holiday weekend!
Informative article, exactly what I wanted to find.
Helpful information. Lucky me I found your site accidentally,
and I’m stunned why this coincidence did not happened earlier!
I bookmarked it.
Hi, the whole thing is going perfectly here and ofcourse every one is sharing facts, that’s genuinely
good, keep up writing.
What’s up colleagues, nice article and good urging
commented at this place, I am genuinely enjoying by these.
I have been surfing online greater than three
hours as of late, yet I by no means discovered any fascinating article like
yours. It is pretty worth enough for me. In my view, if all webmasters and bloggers made excellent content
material as you probably did, the internet will likely be much more useful than ever before.
This is a topic which is close to my heart…
Best wishes! Where are your contact details though?
Pretty section of content. I just stumbled upon your blog and in accession capital to assert that I acquire actually enjoyed account your blog posts.
Any way I will be subscribing to your feeds and even I achievement you access consistently rapidly.
Great goods from you, man. I have 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 entertaining and you still
take care of to keep it smart. I cant wait to read far more from you.
This is really a great web site.
Good post. I learn something totally new and challenging on blogs I stumbleupon everyday.
It will always be interesting to read through content
from other authors and practice something from other sites.
What’s up to every body, it’s my first pay a quick visit of this webpage; this webpage carries awesome
and genuinely excellent stuff in favor of visitors.
Hello.This post was extremely motivating, particularly since I was looking for thoughts on this matter last Friday.
Thankfulness to my father who shared with me
about this web site, this webpage is in fact amazing.
Right now it sounds like Movable Type is the best blogging platform out there right now.
(from what I’ve read) Is that what you are using on your blog?
of course like your web site but you have to take a look at the spelling on several of your posts.
A number of them are rife with spelling problems and I to find it very troublesome to tell the reality
nevertheless I will definitely come back again.
It’s a shame you don’t have a donate button! I’d certainly donate to this outstanding blog!
I suppose for now i’ll settle for book-marking and adding your RSS feed
to my Google account. I look forward to brand new updates and will share
this website with my Facebook group. Chat soon!
Just desire to say your article is as astounding. The clarity in your post is
simply nice and i could assume you are an expert on this subject.
Well with your permission let me to grab your RSS feed to keep up to date
with forthcoming post. Thanks a million and please continue the gratifying work.
Excellent web site. Plenty of helpful information here. I?¦m sending it to some buddies ans additionally sharing in delicious. And of course, thank you in your sweat!
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 will be subscribing to your feeds and even I achievement you access consistently rapidly.