差分总结二 树上差分
树上差分模板题
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;
}
我现在也只有一个保底
太难了
