【BZOJ 3307】雨天的尾巴

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3307
神犇题解:http://blog.csdn.net/ww140142/article/details/48660513

解题报告

这题,搬到序列上大家都会啊
就是先把操作打成tag,扔到序列上
然后用线段树扫一遍,统计答案即可

当然线段树合并也很好写啊
也是先搞成tag,然后合并上去,顺便记录一下答案
时间复杂度:$O(n \log n)$

Code

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

const int N = 100009;
const int M = N << 1;
const int G = 7000000;
const int INF = 1e9;

int n,m,dep[N],ans[N],fa[N][20];
int head[N],to[M],nxt[M];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	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 AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

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) {
			DFS(to[i], w);
		}
	}
}

inline int LCA(int u, int v) {
	if (dep[u]<dep[v]) swap(u, v);
	for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u = fa[u][j];
	if (u == v) return u;
	for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
	return fa[u][0];
}

class Segment_Tree{
	int cnt,ch[G][2],mx[G],id[G],root[N];
	public:
		inline void merge(int x, int y) {
			root[x] = Merge(root[x], root[y]);
		}
		inline void insert(int w, int p, int t) {
			insert(root[w], 1, INF, p, t);
		}
		inline int query(int w) {
			return mx[root[w]]? id[root[w]]: 0;
		}
	private:
		int Merge(int x, int y) {
			if (!x || !y) return x + y;
			if (!ch[x][0] && !ch[x][1]) {
				mx[x] += mx[y];
				return x;
			} else {
				ch[x][0] = Merge(ch[x][0], ch[y][0]);
				ch[x][1] = Merge(ch[x][1], ch[y][1]);
				if (mx[ch[x][0]] >= mx[ch[x][1]]) id[x] = id[ch[x][0]], mx[x] = mx[ch[x][0]];
				else id[x] = id[ch[x][1]], mx[x] = mx[ch[x][1]];
				return x;
			}
		}
		void insert(int &w, int l, int r, int p, int delta) {
			if (!w) w = ++cnt; 
			if (l == r) {
				mx[w] += delta; id[w] = l;
			} else {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, delta);
				else insert(ch[w][1], mid, r, p, delta);
				if (mx[ch[w][0]] >= mx[ch[w][1]]) id[w] = id[ch[w][0]], mx[w] = mx[ch[w][0]];
				else id[w] = id[ch[w][1]], mx[w] = mx[ch[w][1]];
			}
		}
}ST;

void solve(int w, int f) {
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			solve(to[i], w);
			ST.merge(w, to[i]);
		}
	}
	ans[w] = ST.query(w);
}

int main() {
	n = read(); m = read();
	for (int i=1;i<n;i++) AddEdge(read(), read());
	DFS(1, 1);
	for (int j=1;j<20;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	for (int i=1,u,v,lca,c;i<=m;i++) {
		u = read(); v = read(); c = read();
		lca = LCA(u, v);
		ST.insert(u, c, 1);
		ST.insert(v, c, 1);
		ST.insert(lca, c, -1);
		if (lca-1) ST.insert(fa[lca][0], c, -1);		
	}
	solve(1, 1);
	for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

255 thoughts to “【BZOJ 3307】雨天的尾巴”

  1. 704958 589248These kinds of Search marketing boxes normally realistic, healthy and balanced as a result receive just about every customer service necessary for some product. Link Building Services 418921

  2. It is actually a great and helpful piece of information. I?¦m glad that you just shared this useful info with us. Please stay us up to date like this. Thank you for sharing.

  3. Today, I went to the beach with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is completely off topic but I had to tell someone!

  4. Hi, Neat post. There is an issue together with your web site in web explorer, could test this? IE nonetheless is the marketplace chief and a huge component to people will pass over your magnificent writing because of this problem.|

  5. Hi there would you mind letting me know which web host you’re utilizing? I’ve loaded your blog in 3 completely 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!|

  6. Hello there, just turned into aware of your blog through Google, and located that it’s truly informative. I am gonna be careful for brussels. I will be grateful when you continue this in future. Lots of folks shall be benefited out of your writing. Cheers!|

  7. Great article! This is the type of info that are meant to be shared around the internet. Disgrace on the search engines for now not positioning this submit upper! Come on over and seek advice from my website . Thanks =)|

  8. Howdy just wanted to give you a quick heads up and let you know a few of the images aren’t loading correctly. I’m not sure why but I think its a linking issue. I’ve tried it in two different browsers and both show the same outcome.|

  9. Hi, I do think this is a great web site. I stumbledupon it 😉 I’m going to revisit yet again since I saved as a favorite it. Money and freedom is the greatest way to change, may you be rich and continue to guide others.|

  10. Hello! I just wanted to ask if you ever have any problems with hackers? My last blog (wordpress) was hacked and I ended up losing many months of hard work due to no backup. Do you have any methods to protect against hackers?|

  11. I have to thank you for the efforts you have put in writing this blog. I’m hoping to check out the same high-grade content by you later on as well. In fact, your creative writing abilities has inspired me to get my own, personal website now ;)|

  12. Heya! I realize this is kind of off-topic but I had to ask. Does running a well-established website such as yours require a lot of work? I am completely new to blogging but I do write in my journal on a daily basis. I’d like to start a blog so I will be able to share my personal experience and thoughts online. Please let me know if you have any kind of recommendations or tips for new aspiring bloggers. Appreciate it!|

  13. Everything is very open with a really clear explanation of the challenges. It was truly informative. Your website is very useful. Thanks for sharing!|

发表评论

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