题意：
给出一棵\(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;
}