【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;
}

53 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.

发表评论

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