【CodeChef BTREE】Union on Tree

相关链接

题目传送门:https://www.codechef.com/problems/BTREE
数据生成器:http://paste.ubuntu.com/23671176/
中文题面:http://www.codechef.com/download/translated/OCT14/mandarin/BTREE.pdf
官方题解:https://discuss.codechef.com/questions/53273/btree-editorial
神犇题解Ⅰ:http://xllend3.is-programmer.com/posts/64760.html
神犇题解Ⅱ:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes

WJMZBMR Orz

又是 青年计算机科学家陈立杰 出的神题!
真的是跪烂!_(:з」∠)_

解题报告

看一看数据范围就可以知道这题复杂度一定只跟 ∑士兵数 相关
于是考虑先把虚树建出来,那么剩下的问题就是在利用虚树的边来统计答案了

1)函数式线段树的做法

考虑k=1,这样的话不用处理重复的问题,于是直接点分治就可以做
但现在有很多的点,于是我们可以将树剖成很多块,每块中恰好又一个城市a有卫兵
更进一步,我们规定这个联通块中任意一个点i到a的距离不大于到其他任意有卫兵的城市的距离
于是我们如果能在每一个联通块中单独处理每一个卫兵的话,就可以不用考虑去重的问题了

我们再仔细观察一下建出来的虚树,发现每一个块就是虚树上的一部分
对于a所在联通块深度最小的那个点,统计一下、加到答案里去
对于a所在联通块的其余边缘节点,再统计一下、从答案中减去

于是剩下的就是如何具体如何统计一条边对于答案的贡献了
我们分两种情况考虑:

  1. v不是u在虚树中的祖先,统计v的子树中、到u的距离为d的点的个数
    这个的话,直接用函数式线段树查就好
  2. v是u的父亲,其余条件相同
    这样的话,似乎与v的距离就不固定了(lca在u ~ v中移动)
    于是先用点分治做出所有点到u的距离为d的点的个数n1
    然后需要减掉v子树外的部分,这样的话,发现到v的距离就固定了
    于是减掉所有点到v的距离为d-dis(u,v)的点数n2
    再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣!

2)直接用点分治的做法

先用把点分树搞出来,这样就可以O(log^2(n))的时间复杂度内求dis(w,d)
其中dis(w,d)的定义为 到点w距离在d以内的点有多少 (不会的同学可以先去做BZOJ_3730

再考虑把虚树建出来,这样的话唯一的问题就是如何去重了
考虑如果虚树上一条边的两个点的管辖范围没有交集,那么就肯定没有重复
如果有交集,那么设交集的重点为m,交集半径为r'那么直接减掉dis(m,r')就可以辣!

另外还需要预先将完全包含的管辖区间给修改成“相切”的情况,这样才能保证去重完整
还有的话,中点可能落在边上,于是可以在每边的中点加一个点

这样的做法是不是比主席树的做法清真了很多?
然而我还是写了5k+ _ (:з」∠) _
而且如果边带权的话,这题就很难这样做了

Code

最近为什么写啥常数都大到不行啊 QwQ
又是垫底…..

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;

int n,m,T,head[N],to[M],nxt[M],num[N],cost[N];
int anc[N][18],dep[N],val[N],p[N];

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) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

void DFS(int w, int f) {
	static int cnt = 0;
	dep[w] = dep[f] + 1;
	anc[w][0] = f; num[w] = ++cnt;
	for (int i=head[w];i;i=nxt[i]) {
		if (!dep[to[i]]) {
			DFS(to[i], w);
		}
	}
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) 
		if (dep[anc[x][i]] >= dep[y]) 
			x = anc[x][i];
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i];
			y = anc[y][i];
		}
	} 
	return anc[x][0];
}

inline int dis(int x, int y) {
	int lca = LCA(x, y);
	return dep[x] + dep[y] - dep[lca] * 2;
}

class Point_Based_Divide_and_Conquer{
	int fa[N][18],tot[N],sum[N];
	int ans_tmp,root,block_size;
	vector<int> q[N],mul[N];
	bool vis[N];
	
	public: 	
		inline void init() {
			block_size = n;
			ans_tmp = INF;
			Get_Root(1, 1);
			tot[root] = 1;
			build(root, n);	
		}
		
		inline int query(int w, int rag) {
			int ret = Query(w, rag, q);
			for (int i=1,t;i<tot[w];i++) {
				t = rag - dis(fa[w][i], w);
				if (t >= 0) {
					ret += Query(fa[w][i], t, q);
					ret -= Query(fa[w][i-1], t, mul);
				}
			}
			return ret;
		}
	private:
		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(block_size - sum[w], mx);
			if (mx < ans_tmp) {
				ans_tmp = mx;
				root = w;
			}
		}
		
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
					ans_tmp = INF; Get_Root(to[i], w);
					memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
					tot[root] = tot[w] + 1;
					build(root, block_size);
				}
			}
			
			if (val[w]) {
				for (int i=0;i<tot[w];i++) 
					q[fa[w][i]].push_back(dis(w, fa[w][i]));
				for (int i=0;i<tot[w]-1;i++)
					mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));	
			}
			sort(q[w].begin(), q[w].end());
			sort(mul[w].begin(), mul[w].end());
		} 
		
		inline int Query(int w, int r, vector<int> *a) {
			return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
		}
}PDC; 

class Virtual_Tree{
	int stk[N],rag[N],top,lca,cnt,root;
	queue<int> que;
	bool inq[N];
	
	public:	
		inline void build(int &tot) {
			cnt = tot; T = 0;
			root = p[1] = read(); 
			newnode(p[1], read());
			for (int i=2;i<=tot;i++) {
				p[i] = read();
				newnode(p[i], read());
				root = LCA(root, p[i]);
			}
			static auto cmp = [](int a, int b) {return num[a] < num[b];};
			sort(p+1, p+1+tot, cmp);
			if (root != p[1]) p[++tot] = root, newnode(root, -1);
			stk[top=1] = root;
			for (int i=1+(p[1]==root);i<=cnt;i++) {
				lca = LCA(p[i], stk[top]);
				for (;dep[stk[top]] > dep[lca];top--) 
					if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
					else newnode(lca, -1), AddEdge(lca, stk[top]);
				if (lca != stk[top]) 
					stk[++top] = p[++tot] = lca;
				if (p[i] != stk[top])
					stk[++top] = p[i];
			}
			for (int i=1;i<top;i++)
				AddEdge(stk[i], stk[i+1]);
		}
		
		inline int solve(int tot) {
			prework(tot);
			int ret = 0;
			for (int i=1,u,v,r,mid,t;i<T;i+=2) {
				u = to[i]; v = to[i+1];
				r = rag[u] + rag[v] - cost[i] >> 1;
				if (r >= 0) {
					mid = move(u, v, r);
					ret -= PDC.query(mid, r);
				}
			} 
			for (int i=1;i<=tot;i++) 
				ret += PDC.query(p[i], rag[p[i]]);
			return ret;
		}
	private:
		inline void newnode(int w, int v) {
			rag[w] = v << 1;
			head[w] = 0;
		}
		
		inline int move(int x, int y, int r) {
			if (dep[x] < dep[y]) swap(x, y);
			r = rag[x] - r;
			for (int i=0;r;i++,r>>=1)
				if (r & 1) x = anc[x][i];
			return x;	 
		}
		
		inline void prework(int tot) {
			for (int i=1;i<=tot;i++) {
				que.push(p[i]);
				inq[p[i]] = 1;
			}
			
			while (!que.empty()) {
				int w = que.front(); 
				que.pop(); inq[w] = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (rag[w] > rag[to[i]] + cost[i]) {
						rag[to[i]] = rag[w] - cost[i];
						if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
					}
				}
			}
		}
		
		inline void AddEdge(int u, int v) {
			int w = dis(u, v);
			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;
		}
}VT; 

int main() {
	n = read();
	fill(val+1, val+1+n, 1);
	for (int i=1,lim=n,u,v;i<lim;i++) {
		u = read(); v = read();
		Add_Edge(u, ++n);
		Add_Edge(n, v);
	}
	
	DFS(1, 1);
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			anc[i][j] = anc[anc[i][j-1]][j-1];
		}
	}
	PDC.init();
	
	m = read();
	for (int y=1,k;y<=m;y++) {
		VT.build(k = read());
		printf("%d\n",VT.solve(k)); 
	}
	return 0;
}

103 thoughts to “【CodeChef BTREE】Union on Tree”

  1. I’ll right away take hold of your rss feed as I can’t find your email subscription link or newsletter
    service. Do you’ve any? Kindly allow me realize in order that I may just subscribe.
    Thanks.

  2. This is very attention-grabbing, You are an overly professional blogger.
    I’ve joined your feed and stay up for in search of more of your
    great post. Also, I’ve shared your website in my social networks

  3. Simply want to say your article is as astonishing.

    The clarity for your submit is simply excellent and that i can assume you’re a professional in this subject.

    Well along with your permission allow me to snatch your RSS feed to stay updated with imminent post.
    Thank you one million and please continue the rewarding work.

  4. I loved as much as you’ll receive carried out right here.
    The sketch is attractive, your authored subject matter
    stylish. nonetheless, you command get bought an nervousness over that you wish be delivering the following.
    unwell unquestionably come further formerly again as
    exactly the same nearly very often inside case you shield this increase.

  5. I’m amazed, I must say. Rarely do I encounter a blog that’s equally
    educative and interesting, and without a doubt, you have hit the
    nail on the head. The problem is something which not enough folks are speaking
    intelligently about. I am very happy that I came
    across this in my search for something concerning this.

  6. We’re a gaggle of volunteers and starting a brand
    new scheme in our community. Your site offered
    us with valuable information to work on. You’ve performed
    an impressive job and our entire group will probably be thankful to
    you.

  7. I’ve been surfing on-line greater than three hours as of late, but I by no means discovered any fascinating article
    like yours. It is beautiful price enough for me. Personally, if all web owners and bloggers made just right content material as you probably did, the
    net will be a lot more useful than ever before.

  8. I’ve been exploring for a little for any high-quality articles or blog posts on this
    kind of space . Exploring in Yahoo I eventually stumbled upon this website.
    Reading this information So i’m glad to exhibit that I’ve an incredibly good uncanny feeling I discovered exactly what I needed.
    I such a lot unquestionably will make certain to do not fail to remember this web
    site and give it a look on a relentless basis.

  9. I am really inspired together with your writing skills as smartly
    as with the format to your weblog. Is that this a paid subject or did you customize it yourself?
    Either way stay up the nice high quality
    writing, it is uncommon to see a nice weblog like this one these days..

  10. Do you have a spam issue on this blog; I also am a blogger, and I was wanting to know your
    situation; many of us have created some nice practices and we are looking
    to exchange techniques with other folks, be sure to shoot me an email if interested.

  11. You can definitely see your enthusiasm in the article you write.
    The world hopes for even more passionate writers such as you who aren’t afraid to say how
    they believe. Always go after your heart.

  12. Woah! I’m really enjoying the template/theme of this blog.
    It’s simple, yet effective. A lot of times it’s very hard to
    get that “perfect balance” between usability and visual appearance.
    I must say you have done a excellent job with this. Additionally,
    the blog loads very fast for me on Safari. Outstanding Blog!

  13. Great beat ! I wish to apprentice at the same time as you amend your site, how can i
    subscribe for a blog website? The account helped me a applicable deal.

    I had been a little bit acquainted of this your broadcast offered vivid clear concept

  14. Hey very nice web site!! Guy .. Beautiful .. Wonderful ..
    I’ll bookmark your web site and take the feeds additionally?
    I’m happy to find numerous helpful info here within the post, we’d
    like develop more strategies in this regard, thanks for sharing.

    . . . . .

  15. I am extremely impressed with your writing skills and also with
    the layout on your blog. Is this a paid theme or did you modify it yourself?

    Anyway keep up the nice quality writing, it’s rare to see a great blog like
    this one nowadays.

  16. Hello there! I could have sworn I’ve been to this site
    before but after looking at a few of the articles I realized it’s
    new to me. Anyways, I’m definitely happy I discovered it and I’ll be bookmarking it and
    checking back often!

  17. I’ve been exploring for a little bit for any high quality articles
    or blog posts in this kind of space . Exploring in Yahoo I ultimately stumbled upon this site.

    Studying this info So i’m happy to exhibit that I have a very good uncanny feeling I found out exactly what I needed.
    I so much for sure will make certain to don?t overlook this website and give it a glance regularly.
    plenty of fish natalielise

  18. I am not sure where you are getting your info, but good topic.
    I needs to spend some time learning much more or understanding more.
    Thanks for excellent info I was looking for this
    information for my mission.

  19. obviously like your website however you need to take a look
    at the spelling on quite a few of your posts. Several of them are rife with spelling problems and I in finding it very bothersome to
    tell the truth then again I’ll definitely come
    back again.

  20. After I initially left a comment I appear to have clicked the -Notify
    me when new comments are added- checkbox and from now on whenever a comment is added I recieve
    four emails with the exact same comment. Perhaps there is a means you can remove me from
    that service? Kudos!

  21. Unquestionably believe that which you stated.
    Your favorite reason appeared to be on the internet the simplest thing to have in mind
    of. I say to you, I certainly get irked even as folks consider worries that they just don’t recognize about.
    You managed to hit the nail upon the top and also defined out
    the entire thing with no need side effect , folks could take
    a signal. Will likely be again to get more. Thank you

  22. I’m not sure exactly why but this weblog is loading extremely slow
    for me. Is anyone else having this issue or is it a problem on my end?
    I’ll check back later on and see if the problem still exists.

  23. My brother suggested I might like this blog. He was entirely right.
    This publish actually made my day. You can not imagine just how so much time I had spent for this info!

    Thanks!

  24. I have to thank you for the efforts you’ve put in penning
    this website. I really hope to check out the same high-grade blog posts
    by you in the future as well. In truth, your creative writing abilities has encouraged me to get
    my own site now 😉

  25. Howdy! Do you know if they make any plugins to assist with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not
    seeing very good gains. If you know of any please share.
    Appreciate it!

  26. Howdy! I know this is kind of off topic but I was wondering if you knew
    where I could locate a captcha plugin for my comment form?
    I’m using the same blog platform as yours and
    I’m having trouble finding one? Thanks a lot!

  27. I’m truly enjoying the design and layout of your blog. It’s a very
    easy on the eyes which makes it much more enjoyable for me to come here and visit
    more often. Did you hire out a designer to create your theme?
    Great work!

  28. I was extremely pleased to uncover this page.
    I wanted to thank you for your time due to this fantastic read!!
    I definitely liked every part of it and I have you bookmarked
    to look at new information in your blog.

  29. I do consider all the ideas you have introduced in your post.
    They’re really convincing and can definitely work.
    Still, the posts are too quick for newbies. Could you please prolong them a little from subsequent time?
    Thank you for the post.

  30. you are actually a good webmaster. The web site loading pace is amazing.
    It sort of feels that you’re doing any unique trick.
    Also, The contents are masterwork. you have performed
    a wonderful process on this subject!

  31. That is very attention-grabbing, You are a very professional
    blogger. I have joined your rss feed and look forward to in quest of more of your excellent post.
    Also, I have shared your website in my social networks

  32. Hey there would you mind letting me know which webhost you’re utilizing?

    I’ve loaded your blog in 3 different internet browsers and I must say this blog loads a
    lot faster then most. Can you recommend a good web
    hosting provider at a fair price? Thanks a lot, I appreciate it!

  33. Hello there! This article couldn’t be written much better!
    Looking at this post reminds me of my previous roommate!
    He constantly kept preaching about this. I will forward this post to
    him. Pretty sure he’ll have a great read. Many thanks
    for sharing!

  34. I’ve learn several excellent stuff here. Definitely
    worth bookmarking for revisiting. I surprise how a lot attempt
    you set to create this type of wonderful informative site.

  35. Hi there, just became aware of your blog through Google,
    and found that it is really informative. I’m going to watch out for brussels.
    I’ll appreciate if you continue this in future.
    A lot of people will be benefited from your writing.
    Cheers!

  36. Excellent post. Keep writing such kind of information on your blog.
    Im really impressed by your site.
    Hello there, You’ve done a fantastic job. I’ll certainly digg it and
    in my view suggest to my friends. I’m confident they will be benefited from this website.

  37. I think this is one of the most important information for me.
    And i’m glad reading your article. But wanna remark on few
    general things, The site style is ideal, the articles is really excellent :
    D. Good job, cheers

  38. Wonderful blog! I found it while browsing on Yahoo News.

    Do you have any suggestions on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Appreciate it

  39. I just couldn’t depart your site before suggesting that I actually enjoyed the usual information an individual provide
    for your visitors? Is gonna be again incessantly to check up on new posts

  40. My partner and I absolutely love your blog and find many of your post’s to be exactly
    what I’m looking for. Would you offer guest writers to write content for you personally?
    I wouldn’t mind creating a post or elaborating on a number of the subjects you write about here.
    Again, awesome site!

  41. It’s appropriate time to make some plans for the future and it
    is time to be happy. I’ve read this post and if I could I wish to suggest you some interesting things or
    suggestions. Maybe you could write next articles referring to this article.
    I wish to read more things about it!

  42. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your
    point. You definitely know what youre talking about, why waste your intelligence on just posting videos to your weblog when you could be giving us
    something informative to read?

  43. Pretty section of content. I just stumbled upon your weblog
    and in accession capital to assert that I acquire actually enjoyed account your blog posts.

    Any way I will be subscribing to your augment and even I achievement
    you access consistently rapidly.

  44. I do accept as true with all the ideas you’ve introduced in your post.
    They are very convincing and can definitely work. Nonetheless, the posts are too short for newbies.
    May you please extend them a bit from subsequent time?
    Thank you for the post.

  45. Someone necessarily lend a hand to make critically posts I would state.
    That is the very first time I frequented your website
    page and to this point? I amazed with the research you made to make
    this particular publish extraordinary. Magnificent job!

  46. It’s perfect time to make some plans for the future and it’s time to be happy.
    I’ve learn this publish and if I may just I desire to
    recommend you some attention-grabbing issues or
    advice. Maybe you could write next articles regarding this article.
    I desire to learn more issues about it!

  47. Just desire to say your article is as astounding.
    The clarity in your post is simply great and i can assume you are an expert on this subject.

    Fine with your permission allow me to grab your RSS feed to keep
    updated with forthcoming post. Thanks a million and please
    carry on the gratifying work.

  48. Hey there, I think your site might be having browser
    compatibility issues. When I look at your
    website in Ie, it looks fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other
    then that, superb blog!

  49. whoah this blog is magnificent i love studying your posts. Keep up the great work! You understand, many individuals are looking round for this information, you can aid them greatly.

  50. I was wondering if you ever considered changing the layout of your site?
    Its very well written; I love what youve got to say.
    But maybe you could a little more in the way of content so
    people could connect with it better. Youve got an awful lot of
    text for only having one or 2 images. Maybe you could space
    it out better?

  51. Please let me know if you’re looking for a article
    writer for your site. You have some really good posts and I feel I would be
    a good asset. If you ever want to take some of the load off,
    I’d love to write some material for your blog in exchange for a link back to mine.
    Please send me an email if interested. Cheers!

  52. Simply desire to say your article is as astounding.

    The clearness in your post is simply nice and i could assume you’re an expert on this subject.

    Well with your permission allow me to grab your feed to
    keep up to date with forthcoming post. Thanks a million and please continue the enjoyable work.

  53. An outstanding share! I’ve just forwarded this onto a colleague who was
    conducting a little homework on this. And he actually
    bought me lunch simply because I stumbled upon it for him…
    lol. So allow me to reword this…. Thanks for the meal!!
    But yeah, thanx for spending the time to talk about this subject here on your web page.

  54. I think that what you posted was actually very
    logical. But, think about this, suppose you were to write a awesome headline?
    I ain’t saying your information is not good, but what if
    you added something to possibly get a person’s attention? I mean 【CodeChef BTREE】Union on Tree – Qizy's Database is a little vanilla.

    You could look at Yahoo’s front page and note how they write
    article titles to grab people to open the links.

    You might add a related video or a pic or two to get readers interested
    about what you’ve got to say. In my opinion, it might make your posts
    a little livelier.

发表评论

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