题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3829
来来来，让我们来%Claris：http://www.cnblogs.com/clrs97/p/4403170.html
#include<bits/stdc++.h>
using namespace std;
const int N = 500000+9;
const int M = 1000000+9;
int head[N],nxt[M],to[M],g[N],f[N];
int n,tmp[N],beg[N],end[N],tot,C1;
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 Add_Edge(int u, int v) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T;
to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
inline bool CMP(const int &a, const int &b) {
return max(f[a],g[a]+2+f[b]) < (f[b],g[b]+2+f[a]);
}
void DP(int w, int fa) {
int cnt = 0;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != fa) cnt++;
}
beg[w] = tot + 1;
end[w] = (tot += cnt); cnt = -1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != fa) {
DP(to[i],w);
g[w] += g[to[i]] + 2;
tmp[beg[w]+(++cnt)] = to[i];
}
if (beg[w] <= end[w]) {
sort(tmp+beg[w],tmp+end[w]+1,CMP);
}
for (int i=beg[w],sum=0;i<=end[w];i++) {
f[w] = max(f[w], f[tmp[i]] + sum + 1);
sum += g[tmp[i]] + 2;
}
}
int main(){
n = read();
for (int i=1;i<=n;i++) {
f[i] = read();
}
C1 = f[1];
for (int i=1;i<n;i++) {
Add_Edge(read(),read());
}
DP(1,1);
printf("%d\n",max(g[1]+C1,f[1]));
return 0;
}
Hey very nice blog!
Yes! Finally something about quest bars cheap.
Terrific article! This is the kind of information that should
be shared around the net. Shame on Google for not positioning this publish upper!
Come on over and talk over with my site . Thank you =)
Incredible points. Outstanding arguments. Keep up the amazing effort.
My coder is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the expenses.
But he’s tryiong none the less. I’ve been using WordPress on a number of websites for
about a year and am worried about switching to another platform.
I have heard excellent things about blogengine.net. Is there a way I can transfer all my wordpress posts into it?
Any help would be greatly appreciated!
My coder is trying to persuade me to move to .net from PHP.
I have always disliked the idea because of the expenses.
But he’s tryiong none the less. I’ve been using Movable-type on several websites
for about a year and am concerned about switching to another platform.
I have heard very good things about blogengine.net.
Is there a way I can transfer all my wordpress posts into it?
Any kind of help would be really appreciated!
Outstanding post but I was wanting to know if you could write a litte more on this topic?
I’d be very thankful if you could elaborate a little bit more.
Thank you!
Do you have a spam problem on this site; I also am a blogger, and I was wanting to know your situation; many of
us have created some nice procedures and we are looking to exchange techniques with others, please shoot me an e-mail if interested.
I’d like to thank you for the efforts you have put in writing this
blog. I really hope to see the same high-grade blog posts
by you later on as well. In fact, your creative writing abilities
has inspired me to get my very own site now 😉
With havin so much content and articles do you ever run into any issues of plagorism or copyright infringement?
My blog has a lot of exclusive content I’ve either written myself
or outsourced but it seems a lot of it is popping it up all over the internet without my authorization. Do you know any solutions
to help protect against content from being ripped off?
I’d certainly appreciate it.
I was able to find good advice from your blog posts.
Of course, what a fantastic website and informative posts, I will bookmark your website.Best Regards!
An impressive share! I’ve just forwarded this onto
a friend who has been conducting a little homework on this.
And he actually bought me dinner simply because I stumbled upon it for him…
lol. So allow me to reword this…. Thank YOU for the meal!!
But yeah, thanx for spending some time to talk about this subject here on your site.
you are actually a just right webmaster. The site loading pace is amazing.
It kind of feels that you are doing any distinctive trick.
Also, The contents are masterwork. you’ve done a magnificent activity on this matter!
It’s nearly impossible to find experienced people on this subject, but you sound like you know
what you’re talking about! Thanks
Hello, I enjoy reading through your post. I like to write
a little comment to support you.
Hi there, I discovered your web site via Google at the
same time as searching for a related subject, your site got here up, it
appears to be like good. I’ve bookmarked it in my google bookmarks.
Hello there, just became aware of your blog thru Google, and located that it is truly informative.
I am gonna watch out for brussels. I’ll appreciate if you continue
this in future. A lot of other people can be benefited
out of your writing. Cheers!
What a information of un-ambiguity and preserveness of valuable experience concerning unexpected feelings.
Does your blog have a contact page? I’m having trouble locating
it but, I’d like to shoot you an e-mail. I’ve got some ideas for
your blog you might be interested in hearing.
Either way, great site and I look forward to seeing it expand over time.
Thanks for sharing your thoughts about sling tv. Regards
Hi there terrific website! Does running a
blog such as this require a large amount of work?
I’ve absolutely no understanding of coding however I had been hoping to start my own blog in the near future.
Anyways, if you have any ideas or tips for new blog owners please share.
I know this is off subject nevertheless I simply
needed to ask. Thanks a lot!
Definitely believe that which you said. Your favorite reason seemed to be on the internet the easiest thing to be aware of.
I say to you, I definitely get annoyed while people think about worries that they plainly don’t
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 likely be back to get more.
Thanks
Good day I am so glad I found your blog page, I really
found you by error, while I was browsing on Digg for something else, Anyways I am here now
and would just like to say thank you for
a fantastic post and a all round thrilling blog (I also love the theme/design),
I don’t have time to go through it all at the moment but I have bookmarked it and also added in your RSS feeds, so when I have time I will be back to read more, Please do keep up the great work.
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.
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?
Cheers!
You really make it seem so easy with your presentation but I find this topic to be really something that I think I would never understand. It seems too complicated and very broad for me. I’m looking forward for your next post, I will try to get the hang of it!