1 #include <iostream>  2 #include <algorithm>  3 #include <vector>  4 #include <map>  5 #include <cstring>  6 #include <set>  7 #include <bitset>  8 #include <cstdio>  9 #include <cmath> 10 #define esp 1e-8 11 #pragma comment(linker, "/STACK:102400000,102400000") 12 #define in freopen("F:\\rootial\\data\\data.txt", "r", stdin); 13 #define IN freopen("solve_in.txt", "r", stdin); 14 #define out freopen("out.txt", "w", stdout); 15 #define pf(x) ((x)*(x)) 16 #define lowbit(x) ((x)&(-(x))) 17 #define bug(x) printf("Line %d: >>>>>>\n", (x)); 18 #define lson l, m, rt<<1 19 #define rson m+1, r, rt<<1|1 20 #define pb push_back 21 #define mp make_pair 22 #define pi acos(-1.0) 23 #define pf(x) ((x)*(x)) 24  25 using namespace std; 26 typedef long long LL; 27 typedef pair<int, int> PII; 28 typedef map<LL,  LL> MPS; 29 typedef MPS::iterator IT; 30  31 const int maxn = (int)1e5 + 100; 32 LL vv[2][maxn]; 33 int n, m; 34 int top[maxn], num[maxn], tnum[maxn], ID[maxn], son[maxn], sz[maxn], fa[maxn], dep[maxn], tmp[maxn]; 35 int cnt; 36  37 struct Edge 38 { 39     int v, id; 40     Edge() {} 41     Edge(int v, int id):v(v), id(id) {} 42 } edge[maxn*2]; 43 int fi[maxn], nxt[maxn*2]; 44 LL q[2][maxn]; 45  46 void update(int x, LL v[], LL val) 47 { 48     while(x <= n) 49     { 50         v[x] +=val; 51         x += lowbit(x); 52     } 53 } 54 void update(int l, int r, LL val, LL v[]) 55 { 56     update(l, v, val); 57     update(r+1, v, -val); 58 } 59  60 void query(int x, LL &res1, LL &res2) 61 { 62     res1 = 0, res2 = 0; 63     while(x > 0) 64     { 65         res1 += vv[0][x]; 66         res2 += vv[1][x]; 67         x -= lowbit(x); 68     } 69 } 70 void dfs1(int u, int f) 71 { 72     fa[u] = f; 73     dep[u] = dep[f] + 1; 74     sz[u] = 1; 75     for(int i = fi[u]; i; i = nxt[i]) 76     { 77         int v = edge[i].v; 78         int id = edge[i].id; 79         if(v == f) 80             continue; 81         tmp[v] = id; 82         dfs1(v, u); 83         sz[u] += sz[v]; 84         if(sz[son[u]] < sz[v]) 85             son[u] = v; 86     } 87 } 88 void dfs2(int u, int f) 89 { 90     if(son[u]) 91     { 92         num[son[u]] = ++cnt; 93         top[son[u]] = top[u]; 94         ID[tmp[son[u]]] = cnt; 95         dfs2(son[u], u); 96     } 97     for(int i = fi[u]; i; i = nxt[i]) 98     { 99         int v = edge[i].v;100         int id = edge[i].id;101         if(v == f || v == son[u]) continue;102         top[v] = v;103         num[v] = ++cnt;104         ID[tmp[v]] = cnt;105         dfs2(v, u);106     }107 }108 void init()109 {110     for(int i = 0; i <= n; i++)111     {112         vv[0][i] = vv[1][i] = 0;113         son[i] = 0;114         sz[i] = 0;115         fa[i] = 0;116         cnt = 0;117         fi[i] = 0;118         nxt[i<<1] = nxt[i<<1|1] = 0;119         q[0][i] = q[1][i] = 0;120     }121 }122 void add(int u, int v, int x)123 {124     edge[++cnt] = Edge(v, x);125     nxt[cnt] = fi[u];126     fi[u] = cnt;127     edge[++cnt] = Edge(u, x);128     nxt[cnt] = fi[v];129     fi[v] = cnt;130 }131 void input()132 {133     scanf("%d%d", &n, &m);134     init();135     for(int i = 1; i < n; i++)136     {137         int u, v;138         scanf("%d%d", &u, &v);139         add(u, v, i);140     }141     cnt = 0;142 }143 inline bool isdigit(char ch)144 {145     return ch >= ‘0‘ && ch <= ‘9‘;146 }147 const LL B = (int)1e5 + 10;148 149 void update(int u, int v, int k) //dian150 {151     while(top[u] != top[v])152     {153         if(dep[top[u]] < dep[top[v]]) swap(u, v);154         q[0][num[top[u]]] += k;155         q[0][num[u]+1] -= k;156         u = fa[top[u]];157     }158     if(dep[u] < dep[v]) swap(u, v);159     q[0][num[v]] += k;160     q[0][num[u]+1] -= k;161 }162 void update1(int u, int v, int k) //bian163 {164     while(top[u] != top[v])165     {166         if(dep[top[u]] < dep[top[v]]) swap(u, v);167         if(u != top[u])168         {169             q[1][num[son[top[u]]]] += k;170             q[1][num[u]+1] -= k;171         }172         u = top[u];173         q[1][num[u]] += k;174         q[1][num[u]+1] -= k;;175         u = fa[u];176     }177     if(dep[u] < dep[v]) swap(u, v);178     if(u != v)179     {180         q[1][num[son[v]]] += k;181         q[1][num[u]+1] -=  k;182     }183 }184 LL ans[maxn];185 186 void solve()187 {188     dfs1(1, 0);189     top[1] = 1;190     num[1] = ++cnt;191     dfs2(1, 0);192     for(int i = 0; i < m; i++)193     {194         char s[20];195         int u, v, k;196         scanf("%s%d%d%d", s, &u, &v, &k);197         if(strcmp(s, "ADD1") == 0)198         {199             update(u, v, k);200         }201         else202         {203             update1(u, v, k);204         }205     }206     for(int k = 0; k < 2; k++){207             for(int i = 1; i <= n; i++)208                 update(i, vv[k], q[k][i]);209         }210 211     for(int i = 1; i <= n; i++)212     {213         LL res1, res2;214         query(num[i], res1, res2);215         ans[num[i]] = res2;216         printf("%I64d%c", res1, i == n ? ‘\n‘ : ‘ ‘);217     }218     for(int i = 1; i <= n-1; i++)219     {220         LL res = ans[ID[i]];221         printf("%I64d%c", res, i == n-1 ? ‘\n‘ : ‘ ‘);222     }223     if(n == 1)224         puts("");225 }226 int main()227 {228 229     int T;230     for(int t = scanf("%d", &T); t <= T; t++)231     {232         printf("Case #%d:\n", t);233         input();234         solve();235     }236     return 0;237 }