BZOJ3631 Squirrel - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
NOI2014 Day2 废话题解
BZOJ2300 Defence

BZOJ3631 Squirrel

Hoblovski posted @ 2014年8月24日 00:11 in Solutions with tags BZOJ Tarjan LCA ZKW线段树 树链剖分 , 1627 阅读
题意
        给定一棵N个点的树T,以及一个1..N的排列P.
        你最开始在P[1],你需要依次走到P[2]...P[N].
        求每个点被经过几次.
 
Tag 树链剖分,LCA,Tarjan,树上差分
 
没想到现在还回来写题解.
最简单的做法是直接上树链剖分之后就是 1.链加 2.单点查询
树链剖分大法好,ZKW大法好,Pascal 暂定 Rank 1.
 
不过nodgd给出了一种近线性的做法.
转成有根树,对于之后每次链加(u,v),我们在
        u单点加1
        v单点加1
        LCA(u,v)单点减1
        Father(LCA(u,v))单点减1
然后经过次数统计子树和就可以了,正确性显然.LCA可以Tarjan搞.
但是这样会造成一点重复,我们只需要对于u in P[2..N],把u的答案减1即可.
 
以下是树链剖分大法ZKW大法的代码.
program bzoj3631;
  
type tnode=record
        n,next:longint;
     end;
     snode=record
        n,t1:longint;
     end;
  
const maxn=300017;
  
var g,dep,size,fa,son,top,pos,a:array[0..maxn] of longint;
    t:array[0..maxn*5] of longint;
    mem:array[0..maxn shl 1] of tnode;
    v:array[0..maxn] of boolean;
    s:array[0..maxn] of snode;
    n,m,memsize,segsize,rer,zkw:longint;
  
procedure insnbs(u,v:longint);
begin
inc(memsize); with mem[memsize] do begin
        n:=v; next:=g[u];
end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin
        n:=u; next:=g[v];
end; g[v]:=memsize;
end;
  
procedure zkwst_init(n:longint);        begin
zkw:=1; while zkw<n+2 do zkw:=zkw<<1;   end;
  
procedure add(l,r:longint);
begin
inc(l,zkw-1); inc(r,zkw+1);
while l xor r<>1 do begin
        if l and 1=0 then inc(t[l xor 1]);
        if r and 1=1 then inc(t[r xor 1]);
        l:=l>>1; r:=r>>1;
end;
end;
  
procedure dfs1(u:longint);
var head:longint;
begin
fillchar(v,sizeof(v),0); dep[u]:=1; fa[u]:=0;
rer:=1; s[rer].n:=u; s[rer].t1:=g[u]; v[u]:=true;
while rer>0 do begin head:=s[rer].n;
        while (s[rer].t1<>0)and(v[mem[s[rer].t1].n]) do s[rer].t1:=mem[s[rer].t1].next;
        if s[rer].t1=0 then begin
                inc(size[head]);                        inc(size[fa[head]],size[head]);
                if (son[fa[head]]=0)or(size[head]>size[son[fa[head]]]) then
                        son[fa[head]]:=head;
                dec(rer);
        end else begin
                inc(rer);                               s[rer].n:=mem[s[rer-1].t1].n;
                s[rer].t1:=g[s[rer].n];                 v[s[rer].n]:=true;
                dep[s[rer].n]:=dep[head]+1;             fa[s[rer].n]:=head;
        end;
end;
end;
  
procedure dfs2(u:longint);
var head:longint;
begin
fillchar(v,sizeof(v),0); top[u]:=u; segsize:=1; pos[u]:=segsize;
rer:=1; s[rer].n:=u; s[rer].t1:=g[u]; v[u]:=true;
while rer>0 do begin head:=s[rer].n;
        while (s[rer].t1<>0)and(v[mem[s[rer].t1].n]) do s[rer].t1:=mem[s[rer].t1].next;
        if (son[head]<>0)and(not v[son[head]]) then begin
                inc(rer);                               s[rer].n:=son[head];
                s[rer].t1:=g[s[rer].n];                 v[s[rer].n]:=true;
                top[s[rer].n]:=top[head];               inc(segsize);
                pos[s[rer].n]:=segsize;
        end else if s[rer].t1=0 then dec(rer) else begin
                inc(rer);                               s[rer].n:=mem[s[rer-1].t1].n;
                s[rer].t1:=g[s[rer].n];                 v[s[rer].n]:=true;
                top[s[rer].n]:=s[rer].n;                inc(segsize);
                pos[s[rer].n]:=segsize;
        end;
end;
end;
  
procedure pthadd(u,v:longint);
begin
while top[u]<>top[v] do
        if dep[top[u]]>dep[top[v]] then begin
                add(pos[top[u]],pos[u]); u:=fa[top[u]];
        end else begin
                add(pos[top[v]],pos[v]); v:=fa[top[v]];
        end;
if dep[u]<dep[v] then add(pos[u],pos[v])
                 else add(pos[v],pos[u]);
end;
  
procedure init;
var i,j,u,v:longint;
begin
readln(n); for i:=1 to n do read(a[i]); readln;
zkwst_init(n); for i:=1 to n-1 do begin
        readln(u,v); insnbs(u,v);
end; dfs1(1); dfs2(1); for i:=2 to n do t[zkw+pos[a[i]]]:=-1;
end;
  
procedure work;
var i,j:longint;
begin
for i:=1 to n-1 do pthadd(a[i],a[i+1]);
for i:=1 to zkw-1 do begin
        inc(t[i<<1],t[i]); inc(t[i<<1+1],t[i]);
end;
for i:=1 to n do writeln(t[pos[i]+zkw]);
end;
  
begin
init;
work;
end.

 

Avatar_small
John 说:
2021年11月05日 00:03

This blog is so nice to me. I will keep on coming here again and again. Visit my link as well.. fraud investigation

Avatar_small
John 说:
2021年11月05日 14:53

I found that site very usefull and this survey is very cirious, I ' ve never seen a blog that demand a survey for this actions, very curious... شراء لايكات تيك توك

Avatar_small
John 说:
2021年11月07日 19:06

In areas where the cold has begun to thaw out and there are dry sunny days, you know that it is that time of the year again when it is time to rake snow mold off lawns. If the soil is too wet, do not venture out as this may damage the soil. Before starting work in the garden make sure, the soil is crumbly and not sodden. Better Homes and Gardens

Avatar_small
John 说:
2021年11月07日 19:11

As the year comes to an end, you will see plenty of websites offering stock guidance for 2006 and what you should expect for years to come. This guide can be had for free if you buy this or subscribe on that or sign up for newsletters. This is just marketing gimmick. Sure, they have their use. But they want to get you back by offering you a set of stock guide every year. You only need one stock guide for your entire lifetime and I will give it to you for free. Travelzoo Dubai

Avatar_small
John 说:
2021年11月07日 19:16

Want to know more about the fascinating history behind the most famous Christmas tree in London? That's right, we are talking about the time-honoured London tradition of lighting of the Norwegian Christmas Tree in the heart of the famous Trafalgar Square during the Christmas season each year. The beautifully lit Christmas tree and the air filled with the lilting voices of carol singers in the evenings at Trafalgar Square signal the countdown to Christmas for most Londoners. Team Trees Scam

Avatar_small
John 说:
2021年11月09日 00:25 In this article I will explain a few key points about animation and how it can be used in different context. This will give you an insight into the world of animation and help explain some of the methods they use on the big screen. Hope you enjoy the article. download anime
Avatar_small
John 说:
2021年11月09日 15:45

Words are basically names. Sometimes giving something a different name can help give it a fresh perspective. For example, let's look at the word quitting. Giant Inflatable Snow Globe

Avatar_small
John 说:
2021年11月10日 09:38

What creative ways are you working to promote your business? If you have the opportunity to attend any of the available t-shirt printing trade shows, chances are you will meet up with some of the industries greatest companies in the UK. screen printing Cincinnati

Avatar_small
John 说:
2021年11月11日 19:30

Online Sports Betting has been gaining popularity these last few years. The advancements in technology and the internet have contributed greatly in the development and improvement of sports betting. 먹튀폴리스

Avatar_small
John 说:
2021年11月14日 16:04

For any website to become visible on internet we need web hosting facilities. Have you ever thought hosting a web on someone else's behalf? You probably are not aware that it is one of the simplest methods to make a regular monthly income. So what exactly reseller hosting is and how its works? If you keep some steps in mind you can earn a handsome amount every month. Buy wise Verified account

Avatar_small
John 说:
2021年11月15日 15:33

Though the rules of slot machines have changed very little over the years, perhaps few people know that Charles Fey invented the slot machine in 1895. The main difference between the slot of the first of 900 and those that exist today, virtual and physical, is to be found in the electronic system at the heart of the operation. For the rest, now play as it once was: The player operates a lever that activates the wheels on the screen to spin around themselves. pragmatic

Avatar_small
John 说:
2021年11月15日 20:32

Slot Machine gambling addiction is intense, powerful, and highly destructive. Why is slot machine gambling so addictive? judi slot online

Avatar_small
John 说:
2021年11月16日 20:13 Now that you have decided to start your own inflatable rental business, you need to choose the best inflatables to maximize the rental time. This is one of the most important variables for your businesses success. website
Avatar_small
Changing Registered 说:
2021年11月24日 18:03

I hope you understand that how valuable is an email account when it comes to using internet banking, mobile banking services, etc. All the transaction alerts, OTPs, bank statements, etc. are automatically Changing Registered Email ID in HDFC Bank Account received on our email ID nowadays. Though registered mobile number also helps to get all of these. Having an email associated with banking services helps us to keep a double check on all the banking transactions and communications.

Avatar_small
John 说:
2021年11月30日 15:24

You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers. http://69.195.78.97/login/

Avatar_small
John 说:
2021年12月01日 19:41 Unwanted vegetation commonly referred to as weeds can be very troublesome in a well maintained garden or surrounding area such as a patio. If you've spent lots of hours working on your home garden and have great pride in it then an unsightly weed can ruin your hard work. There's lots of varying types of weed killer products currently available and ensuring that you are using the correct one is very very important. buy Cali weed online
Avatar_small
John 说:
2021年12月02日 13:58

Sports betting is a popular pastime among many sports fanatics and others who are looking for thrills. Instead of betting on casino games, whether live or online, many people prefer betting on sports games because they offer more exciting factors, including the skills of the players, historical statistics, and its own slice of chance. But like any other favorite betting endeavor, sports betting also has traps that can lure the ignorant and the uninitiated. 토토사이트

Avatar_small
John 说:
2021年12月05日 14:25

This is really very nice post you shared, i like the post, thanks for sharing.. 707벳

Avatar_small
John 说:
2021年12月06日 14:17

This is a fabulous post I seen because of offer it. It is really what I expected to see trust in future you will continue in sharing such a mind boggling post 세븐 토토

Avatar_small
John 说:
2021年12月08日 02:59

I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. I truly adored reading your posting. Thank you! greatest mathematicans

Avatar_small
John 说:
2021年12月09日 20:48

Thanks for a very interesting blog. What else may I get that kind of info written in such a perfect approach? I’ve a undertaking that I am simply now operating on, and I have been at the look out for such info. 모모벳

Avatar_small
John 说:
2021年12月15日 14:13 If you get into an accident and get hurt as result of it, you should be compensated for the damages. A personal injury lawyer can be a great help in filing for a compensation claim. Personal Injury accidents are very common and can happen any time. toxic baby formula lawyer
Avatar_small
John 说:
2021年12月16日 14:46

Please note that the information provided herein is not legal advice and is provided for informational and educational purposes only. As always, my observations are based on current Ontario laws; you are cautioned not to rely on the information provided herein and that you should do your own due diligent on present and applicable Ontario laws. Ever wonder about the legality and ethics of referral fees between Ontario realtors (note: I use the term "realtors" throughout this blog to mean real estate sales representatives) and lawyers personal injury attorney nashville

Avatar_small
John 说:
2021年12月19日 15:40

Created by LGBTQ.one, THEAPP is a cutting edge PWA (Progressive Web App) that can be used to reduce homophobic interactions with merchants by acting as an LGBTQ-friendly business directory and as a social platform. Connect with friends and find a friendly place to meet up in your city without fear of hostility. gay friendly businesses

Avatar_small
Bank of India Balanc 说:
2021年12月23日 20:29

Bank of India is one of the banks that has come to the fore later but is giving tough competition to all the banks. It is following all the international and national standards of banking.Bank of India Balance Check All the privileges are provided to its customers, and the maximum of them are free of cost, be it internet banking facility, debit and credit card, ATM facility, or any other.

Avatar_small
John 说:
2021年12月29日 15:50

If you don"t mind proceed with this extraordinary work and I anticipate a greater amount of your magnificent blog entries Event Planners

Avatar_small
John 说:
2021年12月31日 20:23 Choosing the right personal injury lawyer may be one of the most important things that you will ever do. If you want to win your case, either as a defense or to win damages, you need to have the right personal injury lawyer fighting by your side. So how do you choose the personal injury lawyer? toxicinfant formula lawsuits
Avatar_small
John 说:
2022年1月01日 15:55

A step by step guide to help you, the unfortunate person that got stuck with the responsibility of planning and implementing a banquet, to put on such a great event that - when all is over - you can glow with pride and bask in the compliments and adoration showered on you by those who attended. Article topics include - PURPOSE, BUDGET, ATTENDANCE, LOCATION, PUBLICITY, TICKETS, ENTERTAINMENT, MENU, and much more... table and chair rentals Palm Desert

Avatar_small
John 说:
2022年1月06日 19:48

Planning a special event can be very stressful. There are many things to consider when choosing which company to rent from. Here are five tips that you can use to help make your next party a huge success. Additional hints

Avatar_small
John 说:
2022年1月06日 22:02

As a hunter in today's world, it can be very grueling to find the best hunting crossbow for the money, until now. We are going to take you through the Top 5 Crossbows of 2022, including the best crossbows for the money, the pros and cons of each, and why you should invest in one. tenpoint crossbow

Avatar_small
John 说:
2022年1月07日 14:28

Very good points you wrote here..Great stuff...I think you've made some truly interesting points.Keep up the good work. nclex test prep

Avatar_small
John 说:
2022年2月05日 21:09

Perhaps one of the best parts of playing poker online is that you have a number of games to choose from. 바둑이

Avatar_small
John 说:
2022年2月13日 13:26 Wow i can say that this is another great article as expected of this blog.Bookmarked this site.. aplikasi angka togel
Avatar_small
John 说:
2022年3月05日 19:45

This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information. Keep it up. Keep blogging. Looking to reading your next post. Dragon Legend

Avatar_small
John 说:
2022年3月19日 19:14

Some of the programs being sold may seem like too good a deal to pass up at only one dollar, but they may be capturing the credit card information for future payments. It is best to read the material thoroughly to be sure that you are not signing up for more payments. is inbox dollars legit

Avatar_small
John 说:
2022年4月13日 15:16

If you don"t mind proceed with this extraordinary work and I anticipate a greater amount of your magnificent blog entries https://vivanet2.com/

Avatar_small
John 说:
2022年4月18日 14:33

You completed certain reliable points there. I did a search on the subject and found nearly all persons will agree with your blog. non pta iphone

Avatar_small
AP SSC Gk Model Pape 说:
2022年9月11日 03:38

General Knowlorge is most important subject to all Class 10 students studying in English Medium, AP SSC Gk ModelPaper Telugu Medium & Urdu Medium of the State Board. So every student who is studying in the state Government & Private Schools can download the AP 10th GK Model Paper 2023 Pdf with answer solutions designed and suggested by subject experts. General Knowlorge is most important subject to all Class 10 students studying in English Medium.

Avatar_small
Bushra 说:
2022年12月28日 19:38

That is really nice to hear. thank you for the update and good luck. scrap car removal Vancouver

Avatar_small
Bushra 说:
2023年1月02日 00:17

Nice to read your article! I am looking forward to sharing your adventures and experiences. Model Escort in Jaipur

Avatar_small
Bushra 说:
2023年1月16日 23:24

Hi! Thanks for the great information you havr provided! You have touched on crucuial points! slope unblocked game

Avatar_small
SEO 说:
2023年1月28日 20:49

thank you for your interesting infomation. เว็บพนันบอล

Avatar_small
SEO 说:
2023年1月29日 02:48

Most of the time I don’t make comments on websites, but I'd like to say that this article really forced me to do so. Really nice post! เว็บพนันบอล

Avatar_small
SEO 说:
2023年2月04日 21:25

Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject. certified pharmacy canada

Avatar_small
SEO 说:
2023年2月19日 20:15

I admit, I have not been on this web page in a long time... however it was another joy to see It is such an important topic and ignored by so many, even professionals. professionals. I thank you to help making people more aware of possible issues. situs slot

Avatar_small
SEO 说:
2023年2月20日 01:54

I have read your blog it is very helpful for me. I want to say thanks to you. I have bookmark your site for future updates. situs slot

Avatar_small
SEO 说:
2023年2月22日 15:39

What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much. 토토커뮤니티

Avatar_small
Bushra 说:
2023年3月08日 08:54

I'm glad I found this web site, I couldn't find any knowledge on this matter prior to.Also operate a site and if you are ever interested in doing some visitor writing for me if possible feel free to let me know, im always look for people to check out my web site. Vancouver crypto exchange

Avatar_small
Bushra 说:
2023年3月13日 04:19

The post is written in very a good manner and it contains many useful information for me. High School Basketball

Avatar_small
Bushra 说:
2023年3月22日 22:33

i read a lot of stuff and i found that the way of writing to clearifing that exactly want to say was very good so i am impressed and ilike to come again in future.. how to start a credit card processing company

Avatar_small
12thmodelquestionpap 说:
2023年5月20日 23:05

writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse 12thmodelquestionpaper.in range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general public interest is a initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India).


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter