SPOJ COT2 Count on a tree II

题目大意

给定一棵n个点的树,每个点有点权。有m次询问,每次查询u,v点间的链上有几种不同颜色的点。
n<=40000 m<=100000

Solution

如果这棵树是一条链,该怎么做呢?最方便的算法肯定是莫队。可以参考PhoenixGS的博客《莫队算法》Orz。它的一个小常数优化,也可以在他的博客中找到,我就不讲了。

但是树上可不可以实现呢?答案是可以的。考虑整棵树的括号序列,每个点入栈时记下它的时间戳,出栈时也记下时间戳。再将每个时间点上的点权记为所代表的点的点权。一棵树就变成一个序列了。这样,我们可以对每组询问进行转化。
如:
其中,黑色代表入栈时间戳,红色代表出时间戳。

如果统计每组询问的两个入时间戳之内的所有数。在上图中,询问E,C点间的链,相当于询问EEFFBC
可以发现,有些点被算了一次,有些点被算了两次,还有些点一次都没被计算。被计算一次的肯定在这条链上,可以先记录下只被计算一次的点的答案。其他点呢?我们需要分类讨论。

假设下面的uv中u的入时间戳小。
如果lca(u,v)=u,即u,v链是一条父子链,只被算了一次的点可以构成整条链(脑补一下)。
否则,u这个点被算了两次,lca(u,v)一次都没算,把答案加上这两个点的贡献就可以。

代码

23 thoughts on “SPOJ COT2 Count on a tree II”

  1. Wonderful post however , 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 further.
    Many thanks!

  2. It’s appropriate time to make some plans for the future and it’s time to be happy.
    I’ve learn this put up and if I may I desire to suggest
    you few attention-grabbing issues or tips. Maybe you could write subsequent articles
    relating to this article. I want to read even more things approximately it!

  3. Good day I am so happy I found your web site,
    I really found you by error, while I was browsing on Google for something else, Anyways I am here now and would just like to say
    cheers for a remarkable post and a all round enjoyable
    blog (I also love the theme/design), I don’t have time to read through it all at the moment but
    I have book-marked it and also included your RSS
    feeds, so when I have time I will be back to read more, Please do keep up the excellent work.

  4. Y᧐u imρly like once we sing praise songs in Church?? Larry
    requested аnd daddy nodded. ?Properly I can make up a worship song.?

    So Larry jumped to his toes and started tο make upp а tune tⲟ a really bаd
    tune. ?Jeѕus iѕ so cool. Its еnjoyable bein with Gоd.
    Hes the funnest God anyone might have.? Larry sang very badly so Lee
    had put hiѕ аrms over his ears.

  5. Someone necessarily lend a hand to make significantly posts I would state.

    That is the very first time I frequented your web page and to this point?
    I amazed with the analysis you made to make this actual publish
    extraordinary. Wonderful activity!

  6. Good day! This post could not be written any better!
    Reading through this post reminds me of my previous room mate!
    He always kept chatting about this. I will forward this page to him.
    Fairly certain he will have a good read. Many thanks for sharing!

  7. Greetings from Idaho! I’m bored at work so I decided to browse your site on my iphone during lunch break.
    I enjoy the information you provide here and can’t wait to take a look when I get home.
    I’m shocked at how fast your blog loaded on my mobile ..
    I’m not even using WIFI, just 3G .. Anyways, superb site!

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注