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

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

发表评论

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