相关链接
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5571
数据生成器：http://paste.ubuntu.com/23672970/
中文题面：http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=651&pid=1004
官方题解：http://oi.cyo.ng/?attachment_id=2084
解题报告
看到位运算，首先想到的就是一位一位独立来搞
酱紫的话，这题就非常简单了
直接上点分树，什么数据结构都不用套，记录零一就可以了
值得注意的是，拆二进制最好拆在最外层
因为拆在里面的话，数组会多一维，寻址的时间消耗大大增加
否则会T到死，不要问我是怎么知道的
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 30000+9;
const int M = N << 1;
const int L = 16;
const int INF = 1e9;
int n,m,T,head[N],to[M],nxt[M],cost[M],ori[N];
int val[N],dep[N],dis[N],fa[N][L],P[N],V[N];
LL ans[N];
inline void Add_Edge(int u, int v, int w) {
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;
}
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;
}
void DFS(int w, int f) {
dep[w] = dep[f] + 1;
fa[w][0] = f;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
DFS(to[i], w);
}
}
}
inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i=L-1;~i;i--) {
if (dep[fa[u][i]] >= dep[v]) {
u = fa[u][i];
}
}
if (u == v) return u;
for (int i=L-1;~i;i--) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
inline int DIS(int u, int v) {
int lca = LCA(u, v);
return dis[u] + dis[v] - dis[lca] * 2;
}
class Node_Based_Divide_and_Conquer{
int area_sz,cur_ans,root,rod[N][L],sum[N];
int anc[N][L],len[N],tos[2][N],tot[2][N];
bool vis[N]; LL f[2][N],sub[2][N];
public:
inline void init() {
memset(vis,0,sizeof(vis));
cur_ans = INF; area_sz = n;
Get_Root(1, 1); len[root] = 1;
Build(root, n);
}
inline void prework() {
memset(f, 0 ,sizeof(f));
memset(sub, 0, sizeof(sub));
memset(tot, 0, sizeof(tot));
memset(tos, 0, sizeof(tos));
}
inline void modify(int w, int t, int p) {
for (int i=0,pre,cur;i<len[w];i++) {
cur = anc[w][i];
f[t][cur] += rod[w][i] * p;
tot[t][cur] += p;
if (i) {
pre = anc[w][i-1];
sub[t][pre] += rod[w][i] * p;
tos[t][pre] += p;
}
}
}
inline LL query(int w, int t, int k) {
LL ret = 0,s,d; t ^= 1;
ret += f[t][w] << k;
for (int i=1,cur,pre;i<len[w];i++) {
cur = anc[w][i]; pre = anc[w][i-1];
d = f[t][cur] - sub[t][pre];
s = tot[t][cur] - tos[t][pre];
ret += d + s * rod[w][i] << k;
}
return ret;
}
private:
void Get_Root(int w, int F) {
sum[w] = 1; int mx = 0;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]] && to[i] != F) {
Get_Root(to[i], w);
mx = max(sum[to[i]], mx);
sum[w] += sum[to[i]];
}
}
mx = max(mx, area_sz - sum[w]);
if (mx < cur_ans) {
cur_ans = mx;
root = w;
}
}
void Build(int w, int sz) {
vis[w] = 1;
anc[w][0] = w;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
area_sz = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w];
cur_ans = INF; Get_Root(to[i], w);
len[root] = len[w] + 1;
memcpy(anc[root]+1, anc[w], sizeof(int)*len[w]);
Build(root, area_sz);
}
}
for (int i=0;i<len[w];i++)
rod[w][i] = DIS(w, anc[w][i]);
}
}NDC;
int main() {
for (LL vout=0;~scanf("%d",&n);vout=T=0) {
memset(head,0,sizeof(head));
memset(ans,0,sizeof(ans));
for (int i=1;i<=n;i++)
ori[i] = read();
for (int i=1,u,v,w;i<n;i++) {
u = read(); v = read(); w = read();
Add_Edge(u, v, w);
}
DFS(1, 1);
for (int j=1;j<L;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
NDC.init();
m = read();
for (int i=1;i<=m;i++) {
P[i] = read();
V[i] = read();
}
for (int j=0;j<L;j++,vout=0) {
memcpy(val,ori,sizeof(ori));
NDC.prework();
for (int i=1;i<=n;i++) {
val[i] >>= j; val[i] &= 1;
NDC.modify(i, val[i], 1);
vout += NDC.query(i, val[i], j);
}
for (int i=1,p,v;i<=m;i++) {
p = P[i]; v = (V[i] >> j) & 1;
vout -= NDC.query(p, val[p], j);
NDC.modify(p, val[p], -1);
NDC.modify(p, v, 1);
vout += NDC.query(p, val[p] = v, j);
ans[i] += vout;
}
}
for (int i=1;i<=m;i++)
printf("%I64d\n",ans[i]);
}
return 0;
}
If some one wants expert view on the topic of blogging then i suggest him/her to visit this webpage, Keep up the
good work.
Very good info. Lucky me I recently found your website by chance (stumbleupon).
I have book marked it for later!
Spot on with this write-up, I seriously believe that this website needs far more attention. I’ll probably be back again to read more, thanks for the information!
Wonderful post! We are linking to this great article on our website.
Keep up the great writing.
Excellent post. Keep posting such kind of info on your
site. Im really impressed by your blog.
Hey there, You have done a great job. I’ll definitely
digg it and personally suggest to my friends.
I am confident they’ll be benefited from
this web site.
Ahaa, its good discussion on the topic of this post at this place at this web site, I have read all that,
so at this time me also commenting here.
Howdy, There’s no doubt that your site may be having internet browser compatibility problems.
When I look at your site in Safari, it looks fine but when opening in Internet Explorer,
it’s got some overlapping issues. I simply wanted to provide you with
a quick heads up! Besides that, excellent blog!
Hello! Quick question that’s completely off topic. Do you know how to make your site
mobile friendly? My weblog looks weird when browsing from my iphone4.
I’m trying to find a theme or plugin that might be able to correct this issue.
If you have any suggestions, please share. Many thanks!
The other day, while I was at work, my sister stole my iphone and tested to see
if it can survive a thirty foot drop, just so she can be a youtube sensation. My apple ipad is now broken and she has 83 views.
I know this is entirely off topic but I had to share it with someone!
Fantastic goods from you, man. I have understand your stuff previous to
and you’re just extremely excellent. I really like what you have acquired here, really like what you’re saying
and the way in which you say it. You make it enjoyable and you still take care of to keep it wise.
I can’t wait to read far more from you. This is really a wonderful web site.
fantastic post, very informative. I ponder why the opposite specialists
of this sector do not understand this. You must proceed
your writing. I am confident, you have a huge readers’ base already!
If some one desires to be updated with hottest technologies after that he must be pay a visit this site and be up to date everyday.
Nice weblog right here! Additionally your website a lot up very fast!
What host are you using? Can I am getting your associate link for your host?
I want my site loaded up as quickly as yours lol
An intriguing discussion is definitely worth comment.
I believe that you need to publish more on this subject,
it may not be a taboo matter but usually people don’t speak about these topics.
To the next! Best wishes!!
I’m impressed, I must say. Rarely do I come across a
blog that’s both educative and amusing, and let me tell you,
you’ve hit the nail on the head. The problem is an issue that
too few men and women are speaking intelligently about. Now i’m
very happy I found this in my hunt for something regarding this.
Wow, awesome blog layout! How long have you been blogging for?
you made blogging look easy. The overall look
of your website is excellent, as well as the content!
I’m not sure why but this blog is loading extremely slow
for me. Is anyone else having this problem or is it a issue on my end?
I’ll check back later on and see if the problem still exists.
It’s a pity you don’t have a donate button! I’d definitely
donate to this fantastic 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 blog with my Facebook group.
Talk soon!
I’m really enjoying the design and layout of your site. It’s a very easy on the eyes which makes it much more pleasant for
me to come here and visit more often. Did you hire
out a developer to create your theme? Fantastic work!
You are so interesting! I don’t think I’ve truly read something like that before.
So nice to discover another person with a few unique thoughts on this topic.
Seriously.. thank you for starting this up.
This website is something that is needed on the internet, someone
with a bit of originality!
Hi! Someone in my Facebook group shared this website with
us so I came to look it over. I’m definitely loving the information. I’m book-marking and will
be tweeting this to my followers! Excellent blog and fantastic design and style.
plenty of fish natalielise
What’s up, after reading this remarkable post i am also cheerful to share my knowledge here
with colleagues.
If some one wishes to be updated with most up-to-date technologies afterward he must be pay a visit this site and be up to date everyday.
I’ve been exploring for a bit for any high-quality articles or weblog posts on this sort of
area . Exploring in Yahoo I ultimately stumbled upon this web site.
Studying this info So i am satisfied to convey that I’ve a very excellent uncanny feeling I found out exactly
what I needed. I such a lot unquestionably will make certain to don?t overlook this website and
provides it a glance regularly. natalielise plenty of fish
Awesome article.
I’m gone to convey my little brother, that he should also
go to see this blog on regular basis to obtain updated from hottest reports.
Spot on with this write-up, I absolutely believe this web site needs
much more attention. I’ll probably be back again to read more, thanks for
the info! natalielise pof
Hello, i feel that i saw you visited my website thus i got here to return the desire?.I am trying to find things to improve my
site!I guess its ok to make use of a few of your ideas!!
Hello there, I found your website via Google whilst looking
for a related subject, your web site came up, it looks great.
I have bookmarked it in my google bookmarks.
Hi there, just changed into aware of your blog through Google,
and found that it is truly informative. I am gonna watch out for brussels.
I’ll be grateful when you continue this in future. Lots
of people might be benefited out of your writing.
Cheers!
This is a topic that is close to my heart… Thank you!
Where are your contact details though?
Hello! This is my 1st comment here so I just wanted to give a
quick shout out and tell you I genuinely enjoy
reading your articles. Can you suggest any other blogs/websites/forums that cover
the same topics? Thanks a lot!
Hi my family member! I want to say that this post is amazing, nice written and come with approximately all
important infos. I would like to look more posts like this .
Yes! Finally something about descargar facebook.
If you desire to increase your familiarity just keep visiting this
web page and be updated with the most up-to-date information posted here.
Hello! I’ve been following your site for a long time now and finally
got the bravery to go ahead and give you a shout out from Atascocita Texas!
Just wanted to tell you keep up the good job!
Thanks on your marvelous posting! I truly enjoyed reading it, you’re a
great author.I will be sure to bookmark your blog and will eventually
come back at some point. I want to encourage you continue your great job,
have a nice evening!
What i don’t understood is in reality how you’re
no longer actually a lot more well-appreciated than you may be right now.
You’re so intelligent. You recognize thus considerably in relation to this subject, produced me individually imagine it from numerous various
angles. Its like men and women are not involved unless it’s something to do with Girl gaga!
Your own stuffs outstanding. Always deal with it up!
I’m really impressed with your writing skills as well as with the layout on your weblog.
Is this a paid theme or did you customize it yourself?
Either way keep up the excellent quality writing, it is rare to see a great blog like
this one these days.
Your style is really unique in comparison to other folks I have read stuff from.
Thank you for posting when you have the opportunity, Guess
I will just book mark this page.
Pretty great post. I simply stumbled upon your weblog and
wanted to mention that I’ve really enjoyed browsing your weblog posts.
In any case I will be subscribing to your rss feed and I hope you write once more very soon!
Fantastic beat ! I wish to apprentice even as you amend your web site,
how could i subscribe for a weblog web site? The account aided me a applicable deal.
I had been a little bit familiar of this your
broadcast provided shiny transparent concept
I don’t even understand how I ended up here, however I assumed this publish used to
be great. I don’t realize who you’re however certainly you are going to
a famous blogger when you aren’t already. Cheers!
Awesome blog! Do you have any tips and hints for aspiring writers?
I’m hoping to start my own blog soon but I’m a little lost on everything.
Would you recommend starting with a free platform like WordPress or go for a paid option? There
are so many choices out there that I’m totally confused ..
Any recommendations? Bless you!
Attractive element of content. I just stumbled upon your website and in accession capital to claim that
I get actually loved account your blog posts. Any way I’ll be subscribing for your feeds
or even I success you get entry to persistently quickly.
Normally I don’t read post on blogs, however I would like
to say that this write-up very forced me to take a look at and do it!
Your writing style has been amazed me. Thanks, quite nice article.
Just wish to say your article is as surprising.
The clearness in your post is simply great and i can assume you
are an expert on this subject. Fine with your permission let me
to grab your RSS feed to keep updated with forthcoming
post. Thanks a million and please continue the enjoyable work.
I am not sure where you are getting your information,
but great topic. I needs to spend some time learning more or understanding more.
Thanks for great info I was looking for this info for my mission.
Hi there, just became alert to your blog through Google,
and found that it is truly informative. I am going to watch out for
brussels. I’ll appreciate if you continue this in future.
Numerous people will be benefited from your writing. Cheers!
Wow, this piece of writing is pleasant, my sister is analyzing these things, so I
am going to let know her.
Hmm is anyone else encountering problems with the pictures on this blog
loading? I’m trying to find out if its a problem on my end or if
it’s the blog. Any feedback would be greatly appreciated.
I have been browsing online greater than three hours nowadays,
yet I never found any attention-grabbing article like yours.
It’s beautiful price sufficient for me. In my view, if all site owners and bloggers made just right content material as you did, the
internet shall be much more helpful than ever before.
I don’t know if it’s just me or if perhaps everybody
else experiencing problems with your website.
It looks like some of the text in your content are running
off the screen. Can somebody else please comment and let me know if this is happening
to them as well? This could be a issue with my internet browser because I’ve had this happen before.
Thank you
Hello there! This is kind of off topic but I need some help
from an established blog. Is it tough to set up your own blog?
I’m not very techincal but I can figure things out pretty quick.
I’m thinking about creating my own but I’m not sure where
to start. Do you have any tips or suggestions? Appreciate
it
I was more than happy to uncover this great site. I need to to thank you for your time due to this wonderful read!!
I definitely appreciated every little bit of it and I have you
saved as a favorite to check out new stuff in your website.
Hi! Someone in my Myspace group shared this site with us so I came to give it a look.
I’m definitely enjoying the information. I’m bookmarking and
will be tweeting this to my followers! Excellent blog and fantastic design and style.
I know this if off topic but I’m looking into starting my own weblog and was wondering what all is required to get setup?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet smart so I’m not 100% certain. Any tips or advice would
be greatly appreciated. Kudos
This piece of writing will assist the internet users
for creating new blog or even a blog from start to end.
Excellent goods from you, man. I have have in mind your stuff prior to and
you’re simply too great. I really like what
you’ve received right here, really like what you are stating and the way in which by which you say it.
You make it enjoyable and you continue to care for to stay it sensible.
I can not wait to learn much more from you. That is actually
a wonderful website.
Today, while I was at work, my sister stole my iPad and tested to see if
it can survive a 25 foot drop, just so she can be a youtube sensation. My apple ipad
is now destroyed and she has 83 views. I know this is completely off
topic but I had to share it with someone!
Please let me know if you’re looking for a article writer for your
blog. You have some really good articles and
I believe I would be a good asset. If you
ever want to take some of the load off, I’d really like
to write some content for your blog in exchange for a link back to mine.
Please shoot me an e-mail if interested. Regards!
My family every time say that I am wasting my time here at net, however I know
I am getting familiarity every day by reading thes pleasant content.
I love your blog.. very nice colors & theme. Did you design this website yourself or did
you hire someone to do it for you? Plz respond as
I’m looking to create my own blog and would like to find out where u got this
from. kudos
Usually I don’t learn post on blogs, however I
would like to say that this write-up very forced me to check out and do so!
Your writing style has been amazed me. Thank you, very nice post.
We’re a group of volunteers and starting a new scheme in our community.
Your website offered us with valuable info to work on. You’ve done a formidable job and our entire community will be grateful to you.
I absolutely love your site.. Great colors & theme.
Did you create this website yourself? Please reply back as I’m trying to create my own site and want to learn where
you got this from or just what the theme is named.
Cheers!
Write more, thats all I have to say. Literally, it
seems as though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your intelligence on just
posting videos to your blog when you could be giving us something enlightening to read?
I was able to find good info from your blog posts.
Asking questions are actually pleasant thing if you are not understanding anything entirely, except this piece of writing presents nice understanding yet.
I enjoy what you guys are usually up too. This type of clever work and reporting!
Keep up the fantastic works guys I’ve incorporated you guys to my own blogroll.
Article writing is also a excitement, if you know after that you can write or else it is complex to write.
An impressive share! I have just forwarded this onto a co-worker who had been conducting
a little homework on this. And he in fact ordered me
breakfast due to the fact that I discovered it for
him… lol. So allow me to reword this…. Thanks for the meal!!
But yeah, thanks for spending time to discuss this subject here on your
website.
This piece of writing will assist the internet visitors
for building up new blog or even a weblog from start
to end.
Hello there! Do you use Twitter? I’d like to follow you if that would be ok.
I’m undoubtedly enjoying your blog and look forward to new posts.
Everyone loves what you guys are up too. This sort of clever work and exposure!
Keep up the amazing works guys I’ve you guys to
my blogroll.
Hello! Do you know if they make any plugins
to safeguard against hackers? I’m kinda paranoid about
losing everything I’ve worked hard on. Any
tips?
It’s really a cool and helpful piece of info.
I am glad that you just shared this useful information with us.
Please keep us informed like this. Thanks for sharing.
Rattling nice pattern and fantastic content material, nothing at all else we want : D.
Hi there, I check your new stuff regularly.
Your writing style is witty, keep up the good work!
My brother recommended I might like this website.
He was totally right. This post truly made my day. You cann’t imagine just how much time I had spent for this information!
Thanks!
I’m now not certain where you’re getting your info, however good topic.
I must spend a while finding out more or understanding more.
Thank you for great information I was on the lookout for this information for my mission.
Excellent blog! Do you have any hints for aspiring writers?
I’m planning to start my own blog soon but I’m a little lost on everything.
Would you propose starting with a free platform like WordPress or go for a paid option? There
are so many options out there that I’m totally confused ..
Any suggestions? Thanks a lot!
Very nice blog post. I certainly appreciate this site.
Stick with it!
I got this web page from my buddy who told me on the topic of this web page and now this
time I am browsing this site and reading very informative articles at this place.
Quality articles is the main to invite the people to go to see the web site, that’s what this web site is providing.
Its like you learn my thoughts! You seem to know a lot
about this, such as you wrote the e-book in it or something.
I feel that you simply can do with a few p.c.
to pressure the message home a little bit, however instead of that,
that is wonderful blog. A fantastic read.
I will certainly be back.
Excellent blog you’ve got here.. It’s hard to
find high quality writing like yours nowadays. I really appreciate
individuals like you! Take care!!
Good day! This is my 1st comment here so I just wanted to give a
quick shout out and tell you I truly enjoy reading
through your blog posts. Can you recommend any other blogs/websites/forums that deal
with the same subjects? Appreciate it!
Please let me know if you’re looking for a writer for your
site. You have some really great articles and I believe I would be a good
asset. If you ever want to take some of the load off, I’d love to write some articles for your blog in exchange for a link
back to mine. Please send me an e-mail if interested. Regards!
Hey, thanks for the blog post. Cool.
This is one awesome blog article.Thanks Again. Really Great.
Muchos Gracias for your blog post.Much thanks again. Keep writing.
Awesome article post. Fantastic.
Hi my loved one! I wish to say that this article is amazing,
nice written and come with almost all important infos.
I’d like to look more posts like this .
I appreciate you sharing this post.Really thank you! Really Cool.
This is one awesome blog article.Really thank you! Awesome.
Thanks a lot for the blog post.Really looking forward to read more. Much obliged.
This is one awesome blog post.Really looking forward to read more. Cool.
Very neat article.Much thanks again. Keep writing.
Appreciate you sharing, great blog post.Really looking forward to read more. Want more.
I really like and appreciate your blog article.Much thanks again. Will read on…
I really liked your article.Really looking forward to read more. Want more.
Thanks again for the article post.Much thanks again. Much obliged.
Very neat blog article.Really looking forward to read more. Awesome.
Great blog post.Much thanks again. Will read on…
wow, awesome article.Really looking forward to read more. Cool.
I loved your blog.Really thank you! Cool.
wow, awesome blog post.Really looking forward to read more. Much obliged.
Hey, thanks for the article post.Much thanks again. Awesome.
A round of applause for your blog. Really Great.
wow, awesome blog article. Really Great.
Perfectly indited articles, Really enjoyed reading.
Great, thanks for sharing this article.Much thanks again. Cool.
A big thank you for your article. Awesome.
Really informative post.Really looking forward to read more. Much obliged.
I really enjoy the post.Really looking forward to read more. Really Cool.
I really enjoy the blog post.Thanks Again. Great.
Hey, thanks for the blog post.Really thank you! Much obliged.
I really liked your article post. Really Great.
Im obliged for the article. Cool.
Great, thanks for sharing this post.Much thanks again. Awesome.
Appreciate you sharing, great article post.Really thank you! Really Great.
Im obliged for the post.Thanks Again. Will read on…
I truly appreciate this blog post.Thanks Again. Keep writing.
This is one awesome blog article.Much thanks again. Want more.
Say, you got a nice blog.Much thanks again. Great.
Muchos Gracias for your article.Much thanks again. Awesome.
Very informative article.Really looking forward to read more. Really Cool.
This is one awesome post.Much thanks again. Keep writing.
Really enjoyed this article.Thanks Again. Will read on…
Thanks a lot for the blog.Really looking forward to read more. Really Cool.
Wow, great blog post.Thanks Again. Really Great.
Very neat blog.Thanks Again. Awesome.
Enjoyed every bit of your blog post. Fantastic.
Hey, thanks for the article post.Much thanks again. Really Cool.
I truly appreciate this article post.Really looking forward to read more. Keep writing.
Thanks for sharing, this is a fantastic blog post. Much obliged.
Very good article.Much thanks again. Keep writing.
Thanks again for the article.Really thank you! Will read on…
I value the article post.Really looking forward to read more. Really Great.
Im thankful for the blog. Great.
Great, thanks for sharing this post.Really thank you!
wow, awesome article.Really thank you! Will read on…
Thank you ever so for you article post.Much thanks again. Great.
Really appreciate you sharing this blog article.Much thanks again. Really Cool.
This is one awesome blog article.Really looking forward to read more. Awesome.
I value the blog.Much thanks again. Cool.
Thanks a lot for the article.Really looking forward to read more. Fantastic.
A big thank you for your blog article. Awesome.
Thanks a lot for the blog post.Really thank you! Great.
I have to be able to voice my passion intended for your kindness giving help to those people that will must have guidance on this kind of important matter.
Really enjoyed this blog article.Much thanks again. Will read on…
Major thanks for the article post.Really looking forward to read more. Cool.
Very neat blog article.Really thank you!
Really informative post.Thanks Again. Want more.
I ‘d refer to that most of us all visitors are endowed to be able to exist in a fantastic place with very several wonderful individuals with very useful things.
Awesome article post. Cool.
오피 사이트 You have the best laugh.