题意：一棵树上两种操作，操作1，改变u到v的每一点的值增加k，操作2，改变u到v每一条边值增加k。最后结束时问，每一点和每一条边的值。
初始时，点和边的值都为0.
分析：
很显然要用树链剖分，将点和边分别划分成连续一段的编号，然后就是维护一段一段的值了，给它增加一个值，由于题目只需要输出最后结果，那么可以用树桩数组维护。
以边为例，对于l~r的每个值增加k，利用树桩数组v[i]表示第i个值与前一个值的差值，那么第k条边的值就是sum{v[i]| 1 <= i <= k},更新时则只要给v[l]加k，给v[r+1]加(- k)， 这个都可以累加下来，最后依次对每个v[i]更新，然后求出结果就行了。
代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <set>
#include <bitset>
#include <cstdio>
#include <cmath>
#define esp 1e-8
#pragma comment(linker, "/STACK:102400000,102400000")
#define in freopen("F:\\rootial\\data\\data.txt", "r", stdin);
#define IN freopen("solve_in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define pf(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define bug(x) printf("Line %d: >>>>>>\n", (x));
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define pb push_back
#define mp make_pair
#define pi acos(-1.0)
#define pf(x) ((x)*(x)) using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef map<LL, LL> MPS;
typedef MPS::iterator IT; const int maxn = (int)1e5 + ;
LL vv[][maxn];
int n, m;
int top[maxn], num[maxn], tnum[maxn], ID[maxn], son[maxn], sz[maxn], fa[maxn], dep[maxn], tmp[maxn];
int cnt; struct Edge
{
int v, id;
Edge() {}
Edge(int v, int id):v(v), id(id) {}
} edge[maxn*];
int fi[maxn], nxt[maxn*];
LL q[][maxn]; void update(int x, LL v[], LL val)
{
while(x <= n)
{
v[x] +=val;
x += lowbit(x);
}
}
void update(int l, int r, LL val, LL v[])
{
update(l, v, val);
update(r+, v, -val);
} void query(int x, LL &res1, LL &res2)
{
res1 = , res2 = ;
while(x > )
{
res1 += vv[][x];
res2 += vv[][x];
x -= lowbit(x);
}
}
void dfs1(int u, int f)
{
fa[u] = f;
dep[u] = dep[f] + ;
sz[u] = ;
for(int i = fi[u]; i; i = nxt[i])
{
int v = edge[i].v;
int id = edge[i].id;
if(v == f)
continue;
tmp[v] = id;
dfs1(v, u);
sz[u] += sz[v];
if(sz[son[u]] < sz[v])
son[u] = v;
}
}
void dfs2(int u, int f)
{
if(son[u])
{
num[son[u]] = ++cnt;
top[son[u]] = top[u];
ID[tmp[son[u]]] = cnt;
dfs2(son[u], u);
}
for(int i = fi[u]; i; i = nxt[i])
{
int v = edge[i].v;
int id = edge[i].id;
if(v == f || v == son[u]) continue;
top[v] = v;
num[v] = ++cnt;
ID[tmp[v]] = cnt;
dfs2(v, u);
}
}
void init()
{
for(int i = ; i <= n; i++)
{
vv[][i] = vv[][i] = ;
son[i] = ;
sz[i] = ;
fa[i] = ;
cnt = ;
fi[i] = ;
nxt[i<<] = nxt[i<<|] = ;
q[][i] = q[][i] = ;
}
}
void add(int u, int v, int x)
{
edge[++cnt] = Edge(v, x);
nxt[cnt] = fi[u];
fi[u] = cnt;
edge[++cnt] = Edge(u, x);
nxt[cnt] = fi[v];
fi[v] = cnt;
}
void input()
{
scanf("%d%d", &n, &m);
init();
for(int i = ; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v, i);
}
cnt = ;
}
inline bool isdigit(char ch)
{
return ch >= '' && ch <= '';
}
const LL B = (int)1e5 + ; void update(int u, int v, int k) //dian
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
q[][num[top[u]]] += k;
q[][num[u]+] -= k;
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
q[][num[v]] += k;
q[][num[u]+] -= k;
}
void update1(int u, int v, int k) //bian
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
if(u != top[u])
{
q[][num[son[top[u]]]] += k;
q[][num[u]+] -= k;
}
u = top[u];
q[][num[u]] += k;
q[][num[u]+] -= k;;
u = fa[u];
}
if(dep[u] < dep[v]) swap(u, v);
if(u != v)
{
q[][num[son[v]]] += k;
q[][num[u]+] -= k;
}
}
LL ans[maxn]; void solve()
{
dfs1(, );
top[] = ;
num[] = ++cnt;
dfs2(, );
for(int i = ; i < m; i++)
{
char s[];
int u, v, k;
scanf("%s%d%d%d", s, &u, &v, &k);
if(strcmp(s, "ADD1") == )
{
update(u, v, k);
}
else
{
update1(u, v, k);
}
}
for(int k = ; k < ; k++){
for(int i = ; i <= n; i++)
update(i, vv[k], q[k][i]);
} for(int i = ; i <= n; i++)
{
LL res1, res2;
query(num[i], res1, res2);
ans[num[i]] = res2;
printf("%I64d%c", res1, i == n ? '\n' : ' ');
}
for(int i = ; i <= n-; i++)
{
LL res = ans[ID[i]];
printf("%I64d%c", res, i == n- ? '\n' : ' ');
}
if(n == )
puts("");
}
int main()
{ int T;
for(int t = scanf("%d", &T); t <= T; t++)
{
printf("Case #%d:\n", t);
input();
solve();
}
return ;
}