经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
洛谷P1600 天天爱跑步(差分 LCA 桶)
来源:cnblogs  作者:自为风月马前卒  时间:2018/11/7 0:16:14  对本文有异议

题意

题目链接

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]\)

  1. #include<bits/stdc++.h>
  2. #define Pair pair<int, int>
  3. #define MP make_pair
  4. #define fi first
  5. #define se second
  6. using namespace std;
  7. const int MAXN = 1e6 + 10, mod = 1e9 + 7, B = 20;
  8. inline int read() {
  9. char c = getchar(); int x = 0, f = 1;
  10. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  11. while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  12. return x * f;
  13. }
  14. int N, M, ans[MAXN], dep[MAXN], top[MAXN], son[MAXN], siz[MAXN], fa[MAXN], S[MAXN],
  15. T[MAXN], w[MAXN], tmp[MAXN], num2[MAXN], sum1[MAXN], sum2[MAXN], Lca[MAXN];
  16. int *num1;//上 -> 下
  17. vector<int> up[MAXN], da[MAXN], dc[MAXN];
  18. vector<int> v[MAXN];
  19. void dfs(int x, int _fa) {
  20. dep[x] = dep[_fa] + 1; siz[x] = 1; fa[x] = _fa;
  21. for(int i = 0, to; i < v[x].size(); i++) {
  22. if((to = v[x][i]) == _fa) continue;
  23. dfs(to, x);
  24. siz[x] += siz[to];
  25. if(siz[to] > siz[son[x]]) son[x] = to;
  26. }
  27. }
  28. void dfs2(int x, int topf) {
  29. top[x] = topf;
  30. if(!son[x]) return ;
  31. dfs2(son[x], topf);
  32. for(int i = 0, to; i < v[x].size(); i++)
  33. if(!top[to = v[x][i]]) dfs2(to, to);
  34. }
  35. int LCA(int x, int y) {
  36. while(top[x] ^ top[y]) {
  37. if(dep[top[x]] < dep[top[y]]) swap(x, y);
  38. x = fa[top[x]];
  39. }
  40. return dep[x] < dep[y] ? x : y;
  41. }
  42. void Deal(int s, int t, int id) {// from s to t
  43. int lca = LCA(s, t); Lca[id] = lca;
  44. up[lca].push_back(s);//from down to up
  45. int dis = dep[s] + dep[t] - 2 * dep[lca];
  46. sum2[s]++;
  47. da[t].push_back(dep[t] - dis);//increase
  48. dc[lca].push_back(dep[t] - dis);//decrase
  49. }
  50. void Find(int x) {
  51. int t1 = num1[dep[x] - w[x]], t2 = num2[dep[x] + w[x]];// 1: 从上往下 2:从下往上
  52. for(int i = 0, to; i < v[x].size(); i++) {
  53. if((to = v[x][i]) == fa[x]) continue;
  54. Find(to);
  55. }
  56. num2[dep[x]] += sum2[x];
  57. for(int i = 0; i < da[x].size(); i++) num1[da[x][i]]++;
  58. ans[x] += num2[dep[x] + w[x]] - t2 + num1[dep[x] - w[x]] - t1;
  59. for(int i = 0; i < up[x].size(); i++) num2[dep[up[x][i]]]--;
  60. for(int i = 0; i < dc[x].size(); i++) num1[dc[x][i]]--;
  61. }
  62. int main() {
  63. //freopen("a.in", "r", stdin); freopen("a.out", "w", stdout);
  64. num1 = tmp + (int)3e5 + 10;
  65. N = read(); M = read();
  66. for(int i = 1; i <= N - 1; i++) {
  67. int x = read(), y = read();
  68. v[x].push_back(y); v[y].push_back(x);
  69. }
  70. dep[0] = -1; dfs(1, 0); dfs2(1, 1);
  71. //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));
  72. for(int i = 1; i <= N; i++) w[i] = read();
  73. for(int i = 1; i <= M; i++) S[i] = read(), T[i] = read(), Deal(S[i], T[i], i);
  74. Find(1);
  75. for(int i = 1; i <= M; i++) if(dep[S[i]] - dep[Lca[i]] == w[Lca[i]]) ans[Lca[i]]--;
  76. for(int i = 1; i <= N; i++) printf("%d ", ans[i]);
  77. return 0;
  78. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号