洛谷P1600 天天爱跑步(差分 LCA 桶)
程序员文章站
2022-05-27 14:36:37
题意 "题目链接" Sol 一步一步的来考虑 $25 \%$:直接$O(nm)$的暴力 链的情况:维护两个差分数组,分别表示从左向右和从右向左的贡献, $S_i = 1$:统计每个点的子树内有多少起点即可 $T_i = 1$:同样还是差分的思想,由于每个点 能对其产生的点的深度是相同的(假设为$x$ ......
题意
sol
一步一步的来考虑
\(25 \%\):直接\(o(nm)\)的暴力
链的情况:维护两个差分数组,分别表示从左向右和从右向左的贡献,
\(s_i = 1\):统计每个点的子树内有多少起点即可
\(t_i = 1\):同样还是差分的思想,由于每个点 能对其产生的点的深度是相同的(假设为\(x\)),那么访问该点时记录下\(dep[x]\)的数量,将结束时\(dep[x]\)的数量与其做差即可
满分做法和上面类似,我们考虑把每个点的贡献都转换到子树内统计
对于每次询问,拆为\(s->lca, lca -> t\)两种(从下到上 / 从上到下)
从上往下需要满足的条件:\(dep[i] - w[i] = dep[t] - len\)
从下往上需要满足的条件:\(dep[i] + w[i] = dep[s]\)
#include<bits/stdc++.h> #define pair pair<int, int> #define mp make_pair #define fi first #define se second using namespace std; const int maxn = 1e6 + 10, mod = 1e9 + 7, b = 20; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, ans[maxn], dep[maxn], top[maxn], son[maxn], siz[maxn], fa[maxn], s[maxn], t[maxn], w[maxn], tmp[maxn], num2[maxn], sum1[maxn], sum2[maxn], lca[maxn]; int *num1;//上 -> 下 vector<int> up[maxn], da[maxn], dc[maxn]; vector<int> v[maxn]; void dfs(int x, int _fa) { dep[x] = dep[_fa] + 1; siz[x] = 1; fa[x] = _fa; for(int i = 0, to; i < v[x].size(); i++) { if((to = v[x][i]) == _fa) continue; dfs(to, x); siz[x] += siz[to]; if(siz[to] > siz[son[x]]) son[x] = to; } } void dfs2(int x, int topf) { top[x] = topf; if(!son[x]) return ; dfs2(son[x], topf); for(int i = 0, to; i < v[x].size(); i++) if(!top[to = v[x][i]]) dfs2(to, to); } int lca(int x, int y) { while(top[x] ^ top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]]; } return dep[x] < dep[y] ? x : y; } void deal(int s, int t, int id) {// from s to t int lca = lca(s, t); lca[id] = lca; up[lca].push_back(s);//from down to up int dis = dep[s] + dep[t] - 2 * dep[lca]; sum2[s]++; da[t].push_back(dep[t] - dis);//increase dc[lca].push_back(dep[t] - dis);//decrase } void find(int x) { int t1 = num1[dep[x] - w[x]], t2 = num2[dep[x] + w[x]];// 1: 从上往下 2:从下往上 for(int i = 0, to; i < v[x].size(); i++) { if((to = v[x][i]) == fa[x]) continue; find(to); } num2[dep[x]] += sum2[x]; for(int i = 0; i < da[x].size(); i++) num1[da[x][i]]++; ans[x] += num2[dep[x] + w[x]] - t2 + num1[dep[x] - w[x]] - t1; for(int i = 0; i < up[x].size(); i++) num2[dep[up[x][i]]]--; for(int i = 0; i < dc[x].size(); i++) num1[dc[x][i]]--; } int main() { //freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); num1 = tmp + (int)3e5 + 10; n = read(); m = read(); for(int i = 1; i <= n - 1; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dep[0] = -1; dfs(1, 0); dfs2(1, 1); //for(int i = 1; i <= n; i++, puts("")) for(int j = 1; j <= n; j++) printf("%d %d %d\n", i, j, lca(i, j)); for(int i = 1; i <= n; i++) w[i] = read(); for(int i = 1; i <= m; i++) s[i] = read(), t[i] = read(), deal(s[i], t[i], i); find(1); for(int i = 1; i <= m; i++) if(dep[s[i]] - dep[lca[i]] == w[lca[i]]) ans[lca[i]]--; for(int i = 1; i <= n; i++) printf("%d ", ans[i]); return 0; }
上一篇: PHP函数比较变量