1 #pragma comment(linker, "/STACK:1024000000,1024000000")  2 #include <cstdio>  3 #include <cstdlib>  4 #include <cstring>  5 #include <iostream>  6 #include <algorithm>  7 using namespace std;  8 typedef unsigned long long ull;  9 typedef long long ll; 10 const int inf = 0x3f3f3f3f; 11 const int maxn = 1e5+10; 12 struct 13 { 14     int  to,next; 15 } e[maxn<<1]; 16 int head[maxn],edge; 17 void add(int x,int y) 18 { 19     e[edge].to = y; 20     e[edge].next = head[x]; 21     head[x] = edge++; 22 } 23  24 int son[maxn],fa[maxn],siz[maxn],dep[maxn]; 25 void dfs1(int root) 26 { 27     siz[root] = 1; 28     son[root] = 0; 29     for (int i = head[root]; i > 0; i = e[i].next) 30     { 31         if (fa[root] != e[i].to) 32         { 33             dep[e[i].to] = dep[root] + 1; 34             fa[e[i].to] = root; 35             dfs1(e[i].to); 36             if (siz[son[root]] < siz[e[i].to]) 37                 son[root] = e[i].to; 38             siz[root] += siz[e[i].to]; 39         } 40     } 41 } 42 int top[maxn],pos[maxn],fp[maxn],tot; 43 void dfs2(int root,int f) 44 { 45     top[root] = f; 46     pos[root] = tot++; 47     fp[pos[root]] = root; 48     if (son[root]>0) 49         dfs2(son[root],top[root]); 50     for (int i = head[root]; i > 0; i = e[i].next) 51         if (fa[root] != e[i].to && e[i].to != son[root]) 52             dfs2(e[i].to,e[i].to); 53 } 54 ll addv[3][maxn<<2]; 55 int k; 56 void pre_update(int ua,int ub,int cho) 57 { 58     int f1 = top[ua]; 59     int f2 = top[ub]; 60     while (f1 != f2) 61     { 62         if (dep[f1] < dep[f2]) 63             swap(f1,f2),swap(ua,ub); 64         addv[cho][pos[f1]] += k; 65         addv[cho][pos[ua]+1] -= k; 66         ua = fa[f1]; 67         f1 = top[ua]; 68     } 69     if (dep[ua] > dep[ub]) 70         swap(ua,ub); 71     if (cho == 1) 72         addv[cho][pos[ua]] += k,addv[cho][pos[ub]+1] -= k; 73     if (cho == 2) 74         addv[cho][pos[son[ua]]] += k,addv[cho][pos[ub]+1] -= k; 75 } 76 int n,m,d[maxn][2],link[maxn]; 77 void init() 78 { 79     scanf ("%d%d",&n,&m); 80     int root = 1; 81     dep[root] = fa[root] = 0; 82     edge = tot = 1; 83     memset(head,0,sizeof(head)); 84     memset(siz,0,sizeof(siz)); 85     memset(addv,0,sizeof(addv)); 86     for (int i = 1; i < n; i++) 87     { 88         int u,v; 89         scanf ("%d%d",&u,&v); 90         d[i][0] = u; 91         d[i][1] = v; 92         add(u,v),add(v,u); 93     } 94     dfs1(root); 95     dfs2(root,root); 96     for (int i = 1; i < n; i++) 97     { 98         if (dep[d[i][0]] < dep[d[i][1]]) 99             swap(d[i][0],d[i][1]);100         link[d[i][0]] = i;101     }102 }103 ll ans1[maxn],ans2[maxn];104 int main(void)105 {106     //freopen("in.txt","r",stdin);107     int t;108     int cas = 1;109     scanf ("%d",&t);110     while (t--)111     {112         init();113         for (int i = 0; i < m; i++)114         {115             char op[10];116             int u,v;117             scanf ("%s%d%d%d",op,&u,&v,&k);118             pre_update(u,v,op[3]-‘0‘);119         }120         for (int i = 1; i <= n; i++)121         {122             addv[1][i] += addv[1][i-1];123             addv[2][i] += addv[2][i-1];124             ans1[fp[i]] = addv[1][i];125             ans2[link[fp[i]]] = addv[2][i];126         }127         printf("Case #%d:\n",cas++);128         printf("%I64d",ans1[1]);129         for (int i = 2; i <= n; i++)130         {131             printf(" %I64d",ans1[i]);132         }133         printf("\n");134         if (n>1)135             printf("%I64d",ans2[1]);136         for (int i = 2; i < n; i++)137         {138             printf(" %I64d",ans2[i]);139         }140         printf("\n");141     }142     return 0;143 }