翻车笔记_ USACO15DEC Max Flow [树上差分, 翻车]

前缀和与差分都能给人意想不到的惊喜

懵逼的 题目

传送至 Luogu (火狐蜜汁上不去…差评)

扯淡的 题解

做差分的时候做的这道题…没错我都知道这是差分了还是WA了…
emmmmm….显然这是区间修改单点查询…于是想到差分…于是就是一道裸的树上差分…啊裆燃还得求个LCA…
然而我一开始想到的是: 记录每一个点和他父亲的差值PC[](又是奇奇怪怪的变量名)…找到两点的LCA, PC[LCA++], PC[s]--, PC[t]--;, 然后从上往下推, 后来发现过不了样例…然后知道如果LCA就是s或者t的话会GG, 所以让LCA的一段保持不变就好了…然后WAWAWAWA…GG
后来发现题解里都是记录sum[]代表一个节点和所有子树的和的差值…然后回溯的时候更新ans…诶为什么这样是对的啊QAQ?
后来发现有这么一种情况

这里写图片描述

如果s = 3, t = 5, 5是LCA, 又是终点, 按理说只应该PC[t]++才对…但是如果只是PC[t]++, 节点6的点权就会受到影响…
所以正确的程序应该是让”其他的子节点”的PC值--, 但是倍增求的LCA似乎并没有办法记录st在LCA的哪一颗子树上…于是GG

改成记录sum[]就A了…

对了今天突然想起来修改的问题…修改的代码大概是这个样的…

1
2
3
4
5
6
7
8
9
scanf("%d%d", &x, &y);
int lcaxy = lca(x, y);

sum[x]++;
sum[y]++;

sum[lcaxy]--;

sum[father[lcaxy]]--;

sum[x]++; sum[y]++; 就是所有以x, y为子树的节点值都要++
sum[lcaxy]--; 因为节点lcaxyx, y两者为子树, 所以其实lcaxy的值是+=2的…所以要--, 来保证节点lcaxy的值也是+=1
sum[father[lcaxy]]--; 因为lcaxy上面(假定有根)的节点都不用变了…所以--好咯…

沙茶的 代码

WA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (50000 + 5)
#define MAXL (20 + 5)
#define MAXQ (100000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int t = a;a = b;b = t;}

const int root = 1;
struct edg
{
int from;
int to;
int next;
}b[MAXN << 1];
int g[MAXN];
int cntb;

int fa[MAXN];
int d[MAXN][MAXL];
int deep[MAXN];
int lgn;

int pc[MAXN];

int n;
int q;

int ans;

void adn(int, int);
int lca(int, int);
void init(int, int);
void dfs(int, int);
int lg(int);
void solve();
void chan(int);
int main()
{
scanf("%d%d", &n, &q);
lgn = lg(n);
int srx, sry;
for (int i = 1; i < n; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
d[root][0] = fa[root] = root;
init(root, 1);
solve();
dfs(root, 0);
printf("%d", ans);
return 0;
}
int lg(int x)
{
for (int i = 1; ; i++)
{
if ((1 << i) > x)
return i;
}
}
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
g[from] = cntb;
}
void init(int dq, int de)
{
deep[dq] = de;
for (int i = 1; i <= lgn; i++)
{
d[dq][i] = d[d[dq][i - 1]][i - 1];
}
for (int i = g[dq]; i; i = b[i].next)
{
if (fa[dq] != b[i].to)
{
d[b[i].to][0] = fa[b[i].to] = dq;
init(b[i].to, de + 1);
}
}
}
int lca(int x, int y)
{
if (deep[x] > deep[y])
{
swap(x, y);
}
for (int i = lgn; i >= 0; i--)
{
if (deep[d[y][i]] >= deep[x])
{
y = d[y][i];
}
}
if (x == y)
return x;
for (int i = lgn; i >= 0; i--)
{
if (d[y][i] != d[x][i])
{
y = d[y][i], x = d[x][i];
}
}
return fa[x];
}
void solve()
{
int srx, sry;
for (int i = 1; i <= q; i++)
{
scanf("%d%d", &srx, &sry);
int lcxy = lca(srx, sry);
++pc[lcxy];
if (lcxy != srx)
chan(srx);
if (lcxy != sry)
chan(sry);
}
}
void chan(int x)
{
for (int i = g[x]; i; i = b[i].next)
{
if (b[i].to != fa[x])
--pc[b[i].to];
}
}
void dfs(int dq, int zh)
{
ans = max(ans, pc[dq] + zh);
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].to != fa[dq])
dfs(b[i].to, zh + pc[dq]);
}
}

/*
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
*/

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (50000 + 5)
#define MAXL (20 + 5)
#define MAXQ (100000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int t = a;a = b;b = t;}

const int root = 1;
struct edg
{
int from;
int to;
int next;
}b[MAXN << 1];
int g[MAXN];
int cntb;

int fa[MAXN];
int d[MAXN][MAXL];
int deep[MAXN];
int lgn;

int pc[MAXN];

int n;
int q;

int ans;

void adn(int, int);
int lca(int, int);
void init(int, int);
void dfs(int);
int lg(int);
void solve();
void chan(int);
int main()
{
scanf("%d%d", &n, &q);
lgn = lg(n);
int srx, sry;
for (int i = 1; i < n; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
d[root][0] = fa[root] = root;
init(root, 1);
solve();
dfs(root);
printf("%d", ans);
return 0;
}
int lg(int x)
{
for (int i = 1; ; i++)
{
if ((1 << i) > x)
return i;
}
}
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
g[from] = cntb;
}
void init(int dq, int de)
{
deep[dq] = de;
for (int i = 1; i <= lgn; i++)
{
d[dq][i] = d[d[dq][i - 1]][i - 1];
}
for (int i = g[dq]; i; i = b[i].next)
{
if (fa[dq] != b[i].to)
{
d[b[i].to][0] = fa[b[i].to] = dq;
init(b[i].to, de + 1);
}
}
}
int lca(int x, int y)
{
if (deep[x] > deep[y])
{
swap(x, y);
}
for (int i = lgn; i >= 0; i--)
{
if (deep[d[y][i]] >= deep[x])
{
y = d[y][i];
}
}
if (x == y)
return x;
for (int i = lgn; i >= 0; i--)
{
if (d[y][i] != d[x][i])
{
y = d[y][i], x = d[x][i];
}
}
return fa[x];
}
void solve()
{
int srx, sry;
for (int i = 1; i <= q; i++)
{
scanf("%d%d", &srx, &sry);
int lcxy = lca(srx, sry);
--pc[lcxy];
--pc[fa[lcxy]];
++pc[srx];
++pc[sry];
}
}
void dfs(int dq)
{
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].to != fa[dq])
{
dfs(b[i].to);
pc[dq] += pc[b[i].to];
}
}
ans = max(ans, pc[dq]);
}

/*
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
*/

By 写pj2017都被吊打的 Cansult