树上差分模板题

P3128 [USACO15DEC]最大流Max Flow

https://www.luogu.org/problem/P3128
找这个树上 重复经过的最多点 经过几次
看这名字 就醉了orz 这题是 树上差分 模板题 点差分

点差分的话 由于 lca 本身是有贡献的 那么d[lca] – 用d[lca父亲] – 只要消掉影响

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int n, m;
int head[maxn], cnt;
int nxt[maxn << 1], to[maxn << 1];
int ans[maxn];

void ade(int a, int b) {
	to[++ cnt] = b;
	nxt[cnt] = head[a], head[a] = cnt;
}

int depth[maxn], fa[maxn][25];
void dfs(int x, int pre) {
	depth[x] = depth[pre] + 1;
	fa[x][0] = pre;
	for(int i = 1; (1 << i) <= depth[x]; i ++)
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(int i = head[x]; i; i = nxt[i])
		if(to[i] != pre) dfs(to[i], x);
}

int LCA(int x, int y) {
	if(depth[x] > depth[y]) swap(x, y);
	for(int i = 24; ~i; -- i) 
		if(depth[x] <= depth[y] - (1 << i))
			y = fa[y][i];
	if(x == y) return x;
	for(int i = 24; ~i; -- i) 
		if(fa[x][i] != fa[y][i])
			x = fa[x][i], y =fa[y][i];
	return fa[x][0];
}

int outans;
void dfsans(int x, int pre) {
	for(int i = head[x]; i; i = nxt[i]) {
		int y = to[i];
		if(y == pre) continue;
		dfsans(y, x);
		ans[x] += ans[y];
	}
	outans = max(outans, ans[x]);
}

signed main() {
	scanf("%d %d", &n, &m);
	for(int i = 1, a, b; i < n; i ++) {
		scanf("%d %d", &a, &b);
		ade(a, b), ade(b, a);
	}
	dfs(1, 0);
	for(int i = 1, a, b; i <= m; i ++) {
		scanf("%d %d", &a, &b);
		int lca = LCA(a, b);
		++ ans[a], ++ans[b], -- ans[lca], -- ans[fa[lca][0]];
	}
	dfsans(1, 0);
	printf("%d\n", outans);
	return 0;
}

P3258 [JLOI2014]松鼠的新家

https://www.luogu.org/problem/P3258
依然是点差分的题
按照题目给的顺序去加 而且 我们要记得减去 除去a1的 其他点 重复经过的的一次 // 这次终点是下一起点
for(int i = 2; i <= n; i ++) ans[id[i]] --; 刚好 最后一个点 因为是厨房 不要糖 我们也正好给剪掉了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;

int n, m;
int head[maxn], cnt;
int nxt[maxn << 1], to[maxn << 1];
int ans[maxn];

void ade(int a, int b) {
	to[++ cnt] = b;
	nxt[cnt] = head[a], head[a] = cnt;
}

int depth[maxn], fa[maxn][25];

void dfs(int x, int pre) {
	depth[x] = depth[pre] + 1;
	fa[x][0] = pre;
	for(int i = 1; (1 << i) <= depth[x]; i ++)
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(int i = head[x]; i; i = nxt[i])
		if(to[i] != pre) dfs(to[i], x);
}

int LCA(int x, int y) {
	if(depth[x] > depth[y]) swap(x, y);
	for(int i = 24; ~i; -- i) 
		if(depth[x] <= depth[y] - (1 << i))
			y = fa[y][i];
	if(x == y) return x;
	for(int i = 24; ~i; -- i) 
		if(fa[x][i] != fa[y][i])
			x = fa[x][i], y =fa[y][i];
	return fa[x][0];
}

int outans;
void dfsans(int x, int pre) {
	for(int i = head[x]; i; i = nxt[i]) {
		int y = to[i];
		if(y == pre) continue;
		dfsans(y, x);
		ans[x] += ans[y];
	}
}

int id[maxn];
signed main() {
	scanf("%d", &n);
	for(int i = 1, x; i <= n; i ++) scanf("%d", &id[i]);
	for(int i = 1, a, b; i < n; i ++) {
		scanf("%d %d", &a, &b);
		ade(a, b), ade(b, a);
	}
	dfs(1, 0);
	for(int i = 1, a, b; i < n; i ++) {
		a = id[i], b = id[i + 1];
// cout << a << " " << b << " ";
		int lca = LCA(a, b);
// cout << lca << endl;
		++ ans[a], ++ans[b], -- ans[lca], -- ans[fa[lca][0]];
	}
	dfsans(1, 0);
	for(int i = 2; i <= n; i ++) ans[id[i]] --;
	for(int i = 1; i <= n; i ++) 
		printf("%d\n", ans[i]);
	return 0;
}

想睡了 还有个 边差分的 + 2个练习题 明天补

P2680 运输计划

这个是边差分
https://www.luogu.org/problem/P2680
我们可以把 一个通道 变成 0 那样的话 我们二分 找他
如果 大于这个边的 找大家都可以最长公用边 然后 最长边 - 他 > mid 就可以找更长的

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;

int n, m;
int head[maxn], cnt;
int nxt[maxn << 1], to[maxn << 1], val[maxn << 1];

void ade(int a, int b, int c) {
	to[++ cnt] = b, val[cnt] = c;
	nxt[cnt] = head[a], head[a] = cnt;
}

int depth[maxn], fa[maxn][25], d[maxn], toval[maxn];
void dfs_lca(int x, int pre) {
	depth[x] = depth[pre] + 1;
	fa[x][0] = pre;
	for(int i = 1; (1 << i) <= depth[x]; i ++)
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(int i = head[x]; i; i = nxt[i])
		if(to[i] != pre) {
			d[to[i]] = d[x] + val[i];
			toval[to[i]] = val[i];
			dfs_lca(to[i], x);
		}
}

int LCA(int x, int y) {
	if(depth[x] > depth[y]) swap(x, y);
	for(int i = 24; ~i; -- i)
		if(depth[x] <= depth[y] - (1 << i))
			y = fa[y][i];
	if(x == y) return x;
	for(int i = 24; ~i; -- i)
		if(fa[x][i] != fa[y][i])
			x = fa[x][i], y =fa[y][i];
	return fa[x][0];
}

int redis(int a, int b) {
	int l = LCA(a, b);
	return d[a] + d[b] - (d[l] << 1);
}

struct node {
	int x, y, l, d;
	bool operator < (const node &a) const {
		return d > a.d;
	} 
} pa[maxn];

int num, ret, coun[maxn];
void dfs(int x, int pre) {
	for(int i = head[x]; i; i = nxt[i]) {
		int y = to[i];
		if(y == pre) continue;
		dfs(y, x);
		coun[x] += coun[y];
	}
	if(coun[x] == num && ret < toval[x]) ret = toval[x];
}
int mlen;
bool chk(int mid) {
	num = 0, ret = 0;
	memset(coun, 0, sizeof coun);
	for(int i = 1; i <= m; i ++)
		if(pa[i].d > mid) {
			++ coun[pa[i].x], ++ coun[pa[i].y], coun[pa[i].l] -= 2;
			++ num;
		} 
	dfs(1, 0);
	//cout << ret << endl;
	return mlen - ret <= mid;
}

signed main() {
	int l = -1, r = -1;
	scanf("%d %d", &n, &m);
	for(int i = 1, a, b, c; i < n; i ++) {
		scanf("%d %d %d", &a, &b, &c);
		ade(a, b, c), ade(b, a, c);
		l = max(l, c);
	}
	dfs_lca(1, 0);
	for(int i = 1, a, b; i <= m; i ++) {
		scanf("%d %d", &a, &b);
		pa[i].x = a, pa[i].y = b;
		pa[i].l = LCA(a, b), pa[i].d = redis(a, b);
		r = max(pa[i].d, r);
	}
	mlen = r;
	l = mlen - l, r = mlen + 1;
	while(l < r) {
		int mid = l + r >> 1;
		if(chk(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
	return 0;
}