P3128 [USACO15DEC]Max Flow P（树上倍增和树链剖分）

思路1（树上倍增$ + $树上差分）

每次都修改一条从$u$到$v$，不就是树上差分的专门操作吗？？

直接用倍增求$LCA$，每次$d[u]++,d[v]++,d[LCA(u,v)]--,d[f[LCA(u,v)][0]]--$。

最后记得算下前缀和。

代码1

#include <iostream>

#include <cstring>

using namespace std;

const int N = 50010,M = 2 * N,MAX_LOG = 20;

int n,m;

int h[N],e[M],ne[M],idx;

int w[N];

int dep[N];

int f[N][MAX_LOG];

void add (int a,int b) {

	e[idx] = b;

	ne[idx] = h[a];

	h[a] = idx++;

}

void dfs1 (int u,int fa) {

	f[u][0] = fa;

	for (int i = 1;i <= MAX_LOG - 1;i++) f[u][i] = f[f[u][i - 1]][i - 1];

	for (int i = h[u];~i;i = ne[i]) {

		int j = e[i];

		if (j == fa) continue;

		dep[j] = dep[u] + 1;

		dfs1 (j,u);

	}

}

int get_LCA (int a,int b) {

	if (dep[a] < dep[b]) swap (a,b);

	for (int i = MAX_LOG - 1;i >= 0;i--) {

		if (dep[f[a][i]] >= dep[b]) a = f[a][i];

	}

	if (a == b) return a;

	for (int i = MAX_LOG - 1;i >= 0;i--) {

		if (f[a][i] != f[b][i]) a = f[a][i],b = f[b][i];

	}

	return f[a][0];

}

int dfs2 (int u,int fa) {

	int ans = 0;

	for (int i = h[u];~i;i = ne[i]) {

		int j = e[i];

		if (j == fa) continue;

		ans = max (ans,dfs2 (j,u));

		w[u] += w[j];

	}

	return max (ans,w[u]);

}

int main () {

	memset (h,-1,sizeof (h));

	cin >> n >> m;

	for (int i = 1;i <= n - 1;i++) {

		int a,b;

		cin >> a >> b;

		add (a,b),add (b,a);

	}

	dfs1 (1,0);

	while (m--) {

		int a,b;

		cin >> a >> b;

		int anc = get_LCA (a,b);

		w[a]++,w[b]++,w[anc]--,w[f[anc][0]]--;

	}

	cout << dfs2 (1,0) << endl;

	return 0;

}

思路2（树链剖分）

修改一条$u$到$v$的路径，查询整棵树的最大值，不就是树剖的模板吗？？

直接套模板（懒得讲

代码2

#include <iostream>

#include <cstring>

using namespace std;

const int N = 50010,M = 2 * N,MAX_LOG = 20;

int n,m;

int h[N],e[M],ne[M],idx;

int timestamp;

int dep[N],s[N],son[N],fa[N];

int id[N],top[N];

struct segment_tree_node {

	int l,r;

	int maxx,add;

}tr[4 * N];

void add (int a,int b) {

	e[idx] = b;

	ne[idx] = h[a];

	h[a] = idx++;

}

void push_up (int u) {

	tr[u].maxx = max (tr[u << 1].maxx,tr[u << 1 | 1].maxx);

}

void push_down (int u) {

	auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1];

	if (root.add) {

		left.maxx += root.add,left.add += root.add;

		right.maxx += root.add,right.add += root.add;

		root.add = 0;

	}

}

void build_segment_tree (int u,int l,int r) {

	if (l == r) {

		tr[u] = {l,r,0,0};

		return ;

	}

	tr[u] = {l,r};

	int mid = l + r >> 1;

	build_segment_tree (u << 1,l,mid),build_segment_tree (u << 1 | 1,mid + 1,r);

	push_up (u);

}

void modify (int u,int l,int r,int d) {

	if (l <= tr[u].l && tr[u].r <= r) {

		tr[u].add += d,tr[u].maxx += d;

		return ;

	}

	push_down (u);

	int mid = tr[u].l + tr[u].r >> 1;

	if (l <= mid) modify (u << 1,l,r,d);

	if (r >= mid + 1) modify (u << 1 | 1,l,r,d);

	push_up (u);

}

int query_max (int u,int l,int r) {

	if (l <= tr[u].l && tr[u].r <= r) return tr[u].maxx;

	push_down (u);

	int mid = l + r >> 1;

	int ans = 0;

	if (l <= mid) ans = max (ans,query_max (u << 1,l,r));

	if (r >= mid + 1) ans = max (ans,query_max (u << 1 | 1,l,r));

	return ans;

}

void dfs1 (int u,int f) {

	dep[u] = dep[f] + 1,s[u] = 1,fa[u] = f;

	for (int i = h[u];~i;i = ne[i]) {

		int j = e[i];

		if (j == f) continue;

		dfs1 (j,u);

		s[u] += s[j];

		if (s[j] > s[son[u]]) son[u] = j;

	}

}

void dfs2 (int u,int top_node) {

	id[u] = ++timestamp,top[u] = top_node;

	if (!son[u]) return ;

	dfs2 (son[u],top_node);

	for (int i = h[u];~i;i = ne[i]) {

		int j = e[i];

		if (j == fa[u] || j == son[u]) continue;

		dfs2 (j,j);

	}

}

void modify_path (int a,int b) {

	while (top[a] != top[b]) {

		if (dep[top[a]] < dep[top[b]]) swap (a,b);

		modify (1,id[top[a]],id[a],1);

		a = fa[top[a]];

	}

	if (dep[a] > dep[b]) swap (a,b);

	modify (1,id[a],id[b],1);

}

int query_subtree (int u) {

	return query_max (1,id[u],id[u] + s[u] - 1);

}

int main () {

	memset (h,-1,sizeof (h));

	cin >> n >> m;

	for (int i = 1;i <= n - 1;i++) {

		int a,b;

		cin >> a >> b;

		add (a,b),add (b,a);

	}

	build_segment_tree (1,1,n),dfs1 (1,0),dfs2 (1,1);

	while (m--) {

		int a,b;

		cin >> a >> b;

		modify_path (a,b);

	}

	cout << query_subtree (1) << endl;

	return 0;

}

巴特西

P3128 [USACO15DEC]Max Flow P（树上倍增和树链剖分）

思路1（树上倍增$ + $树上差分）

代码1

思路2（树链剖分）

代码2

最新文章

热门文章