题意:

给出一棵\(n(1 \leq n \leq 10^5)\)个节点的树,每条边和每个点都有一个权值,初始所有权值为0。

有两种操作:

  • \(ADD1 \, u \, v \, k\):将路径\(u \to v\)上所有节点的权值都加上\(k\)
  • \(ADD2 \, u \, v \, k\):将路径\(u \to v\)上所有边的权值都加上\(k\)

最后输出每个点和边的权值。

分析:

看到树上成段更新,第一反应就是树链剖分,然而这样的算法并不能通过这道题目的数据。

注意到这道题的特殊之处在于多次操作但只有一次查询。

考虑序列上的这样一个问题:

  • 有一个序列\(A\)和有若干次操作,每次让区间\([l,r]\)的元素加上一个值\(k\),最后输出每个元素最终的权值。

    维护一个序列\(B\),使得序列\(A\)是序列\(B\)的前缀和。

    因此,如果将\(B_l\)的权值增加\(k\),那么相当于将\(A_l \sim A_n\)的权值增加\(k\)。

    再将\(B_{r+1}\)的权值减去\(k\),相当于将\(A_{r+1} \sim A_n\)的权值减去\(k\)。

    最终的效果就是将\(A_l \sim A_r\)的权值增加的\(k\),其他位置权值不变。

所以,这样就在\(O(1)\)的时间完成了成段更新。

回到本题上来:受上面思路的启发,我们也可以在某些个点处修改,最后从叶子节点到根节点求一个前缀和得到最终答案。

具体来说就是:

  • 对于点权值的修改:\(B_u, \, B_v\)的权值增加\(k\),\(B_{lca}, \, B_{fa(lca)}\)的权值减少\(k\)
  • 对于边权值的修改:\(B_u, \, B_v\)的权值增加\(k\),\(B_{lca}\)的权值减少\(2k\)

    其中\(lca\)为\(u,v\)的最近公共祖先。

最后还有一个需要注意的地方就是\(n=1\)的情况,输出边权值只需要输出一个空行即可。

也许有更巧妙的写法可以避免这个问题。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long LL;
const int maxn = 100000 + 10; struct Edge
{
int v, nxt;
Edge() {}
Edge(int v, int nxt): v(v), nxt(nxt) {}
}; int ecnt, head[maxn];
Edge edges[maxn * 2]; void AddEdge(int u, int v) {
edges[ecnt] = Edge(v, head[u]);
head[u] = ecnt++;
} int n, m;
int u[maxn],v[maxn];
int fa[maxn], dep[maxn]; LL sum1[maxn], sum2[maxn]; void dfs(int u) {
for(int i = head[u]; ~i; i = edges[i].nxt) {
int v = edges[i].v;
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs(v);
}
} int anc[maxn][20]; void preprocess() {
memset(anc, 0, sizeof(anc));
for(int i = 1; i <= n; i++) anc[i][0] = fa[i];
for(int j = 1; (1 << j) < n; j++)
for(int i = 1; i <= n; i++) if(anc[i][j-1])
anc[i][j] = anc[anc[i][j-1]][j-1];
} int LCA(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int log;
for(log = 0; (1 << log) < dep[u]; log++);
for(int i = log; i >= 0; i--)
if(dep[u] - (1<<i) >= dep[v])
u = anc[u][i];
if(u == v) return u;
for(int i = log; i >= 0; i--)
if(anc[u][i] && anc[u][i] != anc[v][i])
u = anc[u][i], v = anc[v][i];
return fa[u];
} void dfs2(int u) {
for(int i = head[u]; ~i; i = edges[i].nxt) {
int v = edges[i].v;
if(v == fa[u]) continue;
dfs2(v);
sum1[u] += sum1[v];
sum2[u] += sum2[v];
}
} int main()
{
int T; scanf("%d", &T);
for(int kase = 1; kase <= T; kase++) {
scanf("%d%d", &n, &m); ecnt = 0;
memset(fa, 0, sizeof(fa));
memset(dep, 0, sizeof(dep));
memset(head, -1, sizeof(head));
for(int i = 1; i < n; i++) {
scanf("%d%d", u + i, v + i);
AddEdge(u[i], v[i]);
AddEdge(v[i], u[i]);
}
dfs(1);
preprocess(); memset(sum1, 0, sizeof(sum1));
memset(sum2, 0, sizeof(sum2));
while(m--) {
char op[10]; int a, b, k;
scanf("%s", op);
scanf("%d%d%d", &a, &b, &k);
int lca = LCA(a, b);
if(op[3] == '1') {
sum1[a] += k;
sum1[b] += k;
sum1[lca] -= k;
if(lca != 1) sum1[fa[lca]] -= k;
} else {
sum2[a] += k;
sum2[b] += k;
sum2[lca] -= k * 2;
}
} dfs2(1);
for(int i = 1; i < n; i++)
if(dep[u[i]] < dep[v[i]])
swap(u[i], v[i]); printf("Case #%d:\n", kase);
for(int i = 1; i < n; i++) printf("%lld ", sum1[i]);
printf("%lld\n", sum1[n]);
if(n == 1) { puts(""); continue; }
for(int i = 1; i < n - 1; i++)
printf("%lld ", sum2[u[i]]);
printf("%lld\n", sum2[u[n-1]]);
} return 0;
}

最新文章

  1. DBSCAN密度聚类算法
  2. 第一次做socket的一些心得
  3. Python 爬取网站资源文件
  4. Mvc视图引擎、寻址规则
  5. 学习SVG系列(5):SVG渐变
  6. ff
  7. 【Java基础之Object类(一)】Java中Object类中的所有方法(toString、equals、hashCode、clone、finalize、wait和notify等)详解(转载)
  8. 生成ldf数据库文件
  9. Makefile中用宏定义进行条件编译
  10. oracle 行转列 分析函数
  11. 转:Qt项目中遇到的一些小问题汇总
  12. ajax中的stasus错误详解
  13. 关于PHP静态方法调用和实例化类调用的区别
  14. JS限制 获取动太ID,播放视频
  15. Jetson TX1 compile pytorch issues
  16. Python——Django-manage.py的内容
  17. Elasticsearch&#160;Elasticsearch入门指导
  18. DUILIB入门简明教程
  19. 匪警请拨110——C++
  20. php特别值

热门文章

  1. CentOS7.2安装MySql5.7并开启远程连接授权
  2. 笔试题五道spring
  3. zeplin 登录效果实现
  4. c#基础值类和引用类型
  5. 关于ECSHOP中sql注入漏洞修复
  6. css3实现钟表效果
  7. 验证fgets末尾自动添加的字符是'\0&#39; 还是 &#39;\n\&#39;?
  8. 为什么HDFS的副本数通常选择3?
  9. AutoIt 脚本1
  10. Nuget~管理自己的包包