【Codeforces 100633D】LWDB

Qizy 动态点分治, 树, 树分治, 解题报告

相关链接

题目传送门：http://codeforces.com/problemset/gymProblem/100633/D
中文题面：http://paste.ubuntu.com/23661606/

解题报告

直接考虑将其用点分树搞
对于每一个合法的染色，我们尝试在第一个将染色点a和被染色点b分开的分治点c处进行更新
因为是第一个分开的分治点，所以a、b一定在c的不同子树中
不妨设a的染色范围为d，那么对于任意点b来讲，距离c的距离 <= d-dis(a,c)就好

于是修改操作就暴力爬树高，维护一个单调栈
查询操作也是暴力爬树高，在每一个单调栈那里二分出最后生效的染色点即可

Code

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

const int N = 100000+9;
const int M = N << 1;
const int L = 20;
const int INF = 1e9;

int head[N],to[M],nxt[M],cost[M],dis[N],dep[N];
int n,m,fa[N][L];

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, int w) {
	static int T = 0;
	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;
}

void DFS(int w, int f) {
	fa[w][0] = f;
	dep[w] = dep[f] + 1;
	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 DIS(int x, int y) {
	int ret = dis[x] + dis[y];
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=L-1;~i;i--) 
		if (dep[fa[x][i]] >= dep[y]) 
			x = fa[x][i];
	if (x == y) return ret - dis[x] * 2;
	for (int i=L-1;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return ret - dis[fa[x][0]] * 2;
}

class Node_Based_Divide_and_Conquer{
	int cur_ans,root,area_size,rod[N][L];
	int sum[N],vis[N],anc[N][L],len[N];
	struct Data{
		int x,y,z;
		inline bool operator < (const Data &B) const {return x < B.x;}
		inline bool operator <= (const Data &B) const {return x <= B.x;}
	}tmp;
	vector<Data> stk[N];
	vector<Data>::reverse_iterator itr;
	public:
		inline void init() {
			area_size = n; cur_ans = INF;
			Get_Root(1, 1); len[root] = 1;
			Build(root, n);
		}
		inline void modify(int w, int d, int c, int id) {
			tmp.y = c; tmp.z = id;
			for (int i=0,p;i<len[w];i++) {
				p = anc[w][i]; tmp.x = d - rod[w][i];
				if (tmp.x >= 0) {
					while (!stk[p].empty() && stk[p].back() <= tmp) stk[p].pop_back();
					stk[p].push_back(tmp);
				}
			}
		}
		inline int query(int w) {
			Data ret={0,0,0};
			for (int i=0,p;i<len[w];i++) {
				p = anc[w][i]; tmp.x = rod[w][i];
				itr = lower_bound(stk[p].rbegin(), stk[p].rend(), tmp);
				if (itr != stk[p].rend() && ret.z < itr->z) 
					ret = *itr;
			}
			return ret.y;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for  (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]] && to[i] != f) {
					Get_Root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				} 
			} 
			mx = max(mx, area_size - 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_size = 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(anc[w])-4);
					Build(root, area_size);
				}
			}
			for (int i=1;i<len[w];i++)
				rod[w][i] = DIS(w, anc[w][i]);
		}
}NDC;

int main() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	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,v,d,c;i<=m;i++) {
		if (read() == 1) {
			v = read(); d = read();
			NDC.modify(v, d, read(), i);
		} else printf("%d\n",NDC.query(read()));
	}
	return 0;
}

268 thoughts to “【Codeforces 100633D】LWDB”

  34. Hello there, I found your web site by means
    of Google whilst searching for a comparable matter, your site got here up, it seems
    good. I have bookmarked it in my google bookmarks.

    Hi there, simply was alert to your weblog via Google, and located that it’s truly informative.
    I am gonna watch out for brussels. I will be grateful
    if you proceed this in future. Numerous folks will probably be benefited from your writing.
    Cheers!

    Reply

  35. It is perfect time to make some plans for the future and it is time
    to be happy. I have read this post and if I could I wish to suggest you few interesting things or
    suggestions. Maybe you can write next articles referring to this article.
    I wish to read even more things about it!

    Reply

  62. Hello are using WordPress for your site platform?

    I’m new to the blog world but I’m trying to get started and create my own. Do you
    need any coding knowledge to make your own blog?
    Any help would be greatly appreciated!

    Reply

  76. Does your site have a contact page? I’m having trouble locating it but, I’d like to shoot you an email.
    I’ve got some ideas for your blog you might be interested
    in hearing. Either way, great site and I look forward to seeing it develop over
    time.

    Reply

  79. I am no longer certain where you are getting your information, however great topic.
    I must spend a while studying much more or figuring out more.

    Thanks for great info I was in search of this info for my mission.

    Reply

  82. I think that is among the most vital info for me. And i am satisfied reading your article.
    However wanna observation on few general things,
    The web site taste is wonderful, the articles is in point of fact
    excellent : D. Just right activity, cheers

    Reply

  85. Hi there! I know this is kinda off topic but I was wondering which blog platform
    are you using for this website? I’m getting fed up of WordPress because I’ve had problems with hackers and I’m looking at alternatives
    for another platform. I would be great if you could point me in the direction of a good platform.

    Reply

  97. Hey there! I know this is kind of off topic but I was wondering which blog platform are you using for this website?
    I’m getting fed up of WordPress because I’ve had issues with hackers and
    I’m looking at alternatives for another platform.
    I would be great if you could point me in the direction of a
    good platform.

    Reply

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

    Reply

  127. Hi i am kavin, its my first time to commenting anywhere, when i read this piece of writing i thought i could also make comment due to this sensible post.

    Reply

  132. Having read this I believed it was extremely informative.
    I appreciate you spending some time and effort to put this informative article
    together. I once again find myself spending way too much time both
    reading and posting comments. But so what, it was still worthwhile!

    Reply

  148. What’s Going down i am new to this, I stumbled upon this I’ve found It
    positively useful and it has aided me out loads. I hope to give a contribution & assist different users like its helped me.
    Great job.

    Reply

  151. Hi! Do you know if they make any plugins to help with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results.
    If you know of any please share. Many thanks!

    Reply

  153. Very nice post. I just stumbled upon your weblog and wished to say that I’ve really enjoyded surfing around your blog posts. After all I will be subscribing to your feed and I hope you write again very soon!

    Reply

  174. You can definitely see your enthusiasm in the article you write.
    The arena hopes for more passionate writers such as you who are not
    afraid to say how they believe. At all times go after your heart.

    Reply

  179. It’s truly a great and useful piece of info. I’m happy that you just shared this
    helpful information with us. Please stay us up
    to date like this. Thank you for sharing.

    Reply

  181. Great blog here! Also your web site loads up very fast!
    What host are you using? Can I get your affiliate link to your host?
    I wish my web site loaded up as quickly as yours lol

    Reply

  206. Good day! I could have sworn I’ve been to this website before but after looking at some of the articles
    I realized it’s new to me. Anyways, I’m certainly pleased I discovered it and I’ll
    be book-marking it and checking back often!

    Reply

  207. I am writing to let you know of the perfect experience my cousin’s child developed browsing your site. She came to understand so many issues, which included what it’s like to have a wonderful giving character to make many others clearly master specific grueling subject matter. You truly exceeded readers’ expected results. Thanks for distributing those essential, safe, explanatory and in addition fun tips on your topic to Emily.

    Reply

  209. How long does a copyright last on newspaper articles?. . If a service copies newspapers articles and then posts it in a database on the Internet, is there also a copyright on the Internet content?.

    Reply

  232. Definitely believe that which you said. Your favorite justification seemed to be on the internet the easiest thing to be aware of. I say to you, I certainly get annoyed while people think about worries that they plainly don’t know about. You managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people can take a signal. Will probably be back to get more. Thanks|

    Reply

  236. Greetings from Carolina! I’m bored to tears at work so I decided to browse your website on my iphone during lunch break. I really like the information you provide here and can’t wait to take a look when I get home. I’m shocked at how quick your blog loaded on my cell phone .. I’m not even using WIFI, just 3G .. Anyways, very good site!|

    Reply

  245. Hey There. I found your blog the usage of msn. That is a very well written article. I’ll be sure to bookmark it and return to read more of your useful info. Thank you for the post. I’ll definitely return.|

    Reply

  249. Hey exceptional website! Does running a blog similar to this take a large amount of work? I have virtually no expertise in programming however I had been hoping to start my own blog soon. Anyway, should you have any recommendations or techniques for new blog owners please share. I know this is off subject but I simply needed to ask. Thank you!|

    Reply

  255. I think what you said made a lot of sense. However, what about this? suppose you wrote a catchier title? I ain’t saying your content isn’t solid, however suppose you added a headline that grabbed a person’s attention? I mean BLOG_TITLE is a little plain. You could peek at Yahoo’s home page and see how they create post titles to grab viewers to click. You might try adding a video or a related pic or two to grab readers interested about everything’ve written. Just my opinion, it might make your posts a little bit more interesting.|

    Reply

  261. Wonderful site. Plenty of helpful info here. I’m sending it to some buddies ans also sharing in delicious. And of course, thank you in your sweat!|

    Reply

  262. Right here is the perfect site for anyone who wants to find out about this topic. You know a whole lot its almost tough to argue with you (not that I personally will need to…HaHa). You certainly put a fresh spin on a topic that has been written about for decades. Excellent stuff, just wonderful!|

    Reply

  267. Sweet blog! I found it while surfing around on Yahoo News. Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Thanks|

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *