1 #include<iostream>  2 #include<stdio.h>  3 #include<string.h>  4 #include <string>  5 #include <cmath>  6 #include <algorithm>  7 #include <map>  8 #include <set>  9 #include <queue> 10 #include <stack> 11 #include<stdlib.h> 12 #include <vector> 13 using namespace std; 14 #pragma comment(linker, "/STACK:1024000000,1024000000") 15 #define ll __int64 16 #define CL(a,b) memset(a,b,sizeof(a)) 17 #define MAXNODE 100010 18  19 int n,q; 20  21 typedef struct myedge 22 { 23     int v,next,p; 24 }E; 25  26 E edge[MAXNODE*2]; 27 int head[MAXNODE],ce; 28  29 void inithead() 30 { 31     CL(head,-1); 32     ce=0; 33 } 34 void addedge(int s,int e,int p) 35 { 36     edge[ce].p=p;edge[ce].v=e;edge[ce].next=head[s];head[s]=ce++; 37     edge[ce].p=p;edge[ce].v=s;edge[ce].next=head[e];head[e]=ce++; 38 } 39  40 typedef struct opedge 41 { 42     int v,t,k,p,next; 43 }O; 44  45 O op[MAXNODE*2]; 46 int heado[MAXNODE],co; 47 int etn[MAXNODE]; 48  49 void initheado() 50 { 51     CL(heado,-1); 52     CL(etn,0); 53     co=0; 54 } 55  56 void addo(int s,int e,int t,int k,int p) 57 { 58     op[co].t=t;op[co].v=e;op[co].next=heado[s];op[co].p=p;op[co].k=k;heado[s]=co++; 59     op[co].t=t;op[co].v=s;op[co].next=heado[e];op[co].p=p;op[co].k=k;heado[e]=co++; 60 } 61  62 int fa[MAXNODE]; 63 int fifa(int i) 64 { 65     if(fa[i]==i)return i; 66     fa[i]=fifa(fa[i]); 67     return fa[i]; 68 } 69  70 int pre[MAXNODE]; 71 int tagp[MAXNODE]; 72 ll  re[MAXNODE][2]; 73 int tag[MAXNODE]; 74  75 void initdfs() 76 { 77     CL(pre,-1); 78     CL(tagp,0); 79     CL(tag,0); 80     CL(re,0); 81     for(int i=0;i<MAXNODE;i++)fa[i]=i; 82 } 83  84 void dfsad(int i,int pr) 85 { 86     pre[i]=pr; 87     int p=head[i],v,t,k,pos,rt; 88     while(p!=-1) 89     { 90         v=edge[p].v; 91         if(pre[v]==-1) 92         { 93             etn[edge[p].p]=v; 94             dfsad(v,i); 95         } 96         p=edge[p].next; 97     } 98     tag[i]=1; 99     p=heado[i];100     while(p!=-1)101     {102         v=op[p].v;103         t=op[p].t;104         k=op[p].k;105         rt=fifa(v);106         if(tag[v]==1&&tagp[op[p].p]==0)107         {108             re[i][t]+=k;re[v][t]+=k;109             re[rt][t]-=k;110             if(t==0)111             {112                 re[pre[rt]][t]-=k;113             }114             else re[rt][t]-=k;115             tagp[op[p].p]=1;116         }117         p=op[p].next;118     }119     fa[i]=pr;120 }121 122 void dfs(int i,int pr)123 {124     tag[i]=1;125     int p=head[i],v;126     while(p!=-1)127     {128         v=edge[p].v;129         if(tag[v]==0)dfs(v,i);130         p=edge[p].next;131     }132     re[pr][0]+=re[i][0];133     re[pr][1]+=re[i][1];134 }135 136 char opt[10];137 138 int main()139 {140     int tt,ii;141     cin>>tt;142     for(ii=1;ii<=tt;ii++)143     {144         scanf("%d %d",&n,&q);145         int i,j,a,b,k;146         inithead();147         initheado();148         initdfs();149         for(i=1;i<n;i++)150         {151             scanf("%d %d",&a,&b);152             addedge(a,b,i);153         }154         for(i=1;i<=q;i++)155         {156             scanf("%s %d %d %d",opt,&a,&b,&k);157             {158                 if(opt[3]==‘1‘)159                 {160                     addo(a,b,0,k,i);161                 }162                 else163                 {164                     addo(a,b,1,k,i);165                 }166             }167         }168         dfsad(1,0);169         CL(tag,0);170         dfs(1,0);171         printf("Case #%d:\n",ii);172         for(i=1;i<=n;i++)173         {174             if(i!=1)printf(" ");175             printf("%I64d",re[i][0]);176         }cout<<endl;177         for(i=1;i<n;i++)178         {179             if(i!=1)printf(" ");180             printf("%I64d",re[etn[i]][1]);181         }cout<<endl;182     }183     return 0;184 }