You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N

There are N - 1 edges numbered from 1 to N - 1.

Each node has a value and each edge has a value. The initial value is 0.

There are two kind of operation as follows:

● ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k.

● ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k.

After finished M operation on the tree, please output the value of each node and edge.

 

The first line of the input is T (1 ≤ T ≤ 20), which stands for the number of test cases you need to solve.

The first line of each case contains two integers N ,M (1 ≤ N, M ≤10⁵),denoting the number of nodes and operations, respectively.

The next N - 1 lines, each lines contains two integers u, v(1 ≤ u, v ≤ N ), denote there is an edge between u,v and its initial value is 0.

For the next M line, contain instructions “ADD1 u v k” or “ADD2 u v k”. (1 ≤ u, v ≤ N, -10⁵ ≤ k ≤ 10⁵)

 

For each test case, print a line “Case #t:”(without quotes, t means the index of the test case) at the beginning.

The second line contains N integer which means the value of each node.

The third line contains N - 1 integer which means the value of each edge according to the input order.

 

 

 

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 2e5+, M = 1e3+, mod = 1e9+, inf = 2e9;

int dep[N],head[N],t=,sz[N],fa[N],indexS,top[N],pos[N],son[N],idpos[N];

struct ss{int to,next,id;}e[N*];

int n;

void add(int u,int v,int id)

{e[t].to = v;e[t].next = head[u];e[t].id=id;head[u] = t++;}

void dfs(int u) {

    int k = ;

    sz[u] = ;

    dep[u] = dep[fa[u]] + ;

    for(int i = head[u]; i; i = e[i].next) {

        int to = e[i].to;

        if(to == fa[u]) continue;

        fa[to] = u;

        idpos[to] = e[i].id;

        dfs(to);

        sz[u] += sz[to];

        if(sz[to] > sz[k]) k = to;

    }

    if(k) son[u] = k;

}

void dfs(int u,int chain) {

    int k = ;

    pos[u] = ++indexS;

    top[u] = chain;

    if(son[u] > )

        dfs(son[u],chain);

    for(int i = head[u]; i; i = e[i].next) {

        int to = e[i].to;

        if(dep[to] > dep[u] && son[u] != to)

            dfs(to,to);

    }

}

LL sum[N],sum2[N];

void updateL(int x,int y,int k) {

    while(top[x] != top[y]) {

        if(dep[top[x]] < dep[top[y]]) swap(x,y);

        sum2[pos[top[x]]] +=k;

        sum2[pos[x]+] -=k;

        x = fa[top[x]];

    }

    if(dep[x] < dep[y]) swap(x,y);

    sum2[pos[y]] +=k;

    sum2[pos[x]+] -=k;

}

void updateW(int x,int y,int k) {

    while(top[x] != top[y]) {

        if(dep[top[x]] < dep[top[y]]) swap(x,y);

        sum[pos[top[x]]] += k;

        sum[pos[x] + ] -= k;

        x = fa[top[x]];

    }

    if(dep[x] > dep[y]) swap(x,y);

    sum[pos[x] + ] += k;

    sum[pos[y] + ] -= k;

}

void init() {

    t = ;

    memset(head,,sizeof(head));

    indexS = ;fa[] = ;

    for(int i = ; i <= n+; ++i) sum[i] = , sum2[i] = ;

    for(int i = ; i <= n; ++i) son[i] = ,sz[i] = ;

}

int T,m,cas = ;

LL f[N];

int main() {

    scanf("%d",&T);

    while(T--) {

      scanf("%d%d",&n,&m);

        init();

        for(int i =  ; i < n; ++i) {

            int x,y;

            scanf("%d%d",&x,&y);

            add(x,y,i),add(y,x,i);

        }

        dfs();

        dfs(,);

        while(m--) {

            char ch[];

            int x,y,k;

            scanf("%s",ch);

           scanf("%d%d%d",&x,&y,&k);

            if(ch[] == '') {

                updateL(x,y,k);

            }

            else if(x!=y){

                updateW(x,y,k);

            }

        }

        printf("Case #%d:\n",cas++);

        for(int i = ; i <= n; ++i)

            sum[i]+=sum[i-],sum2[i]+=sum2[i-];

        for(int i = ; i <= n; ++i) f[idpos[i]] = sum[pos[i]];

        for(int i = ; i < n; ++i)

            printf("%I64d ",sum2[pos[i]]);

        printf("%I64d\n",sum2[pos[n]]);

        for(int i = ; i < n-; ++i) printf("%I64d ",f[i]);

        if(n- > )printf("%I64d",f[n-]);

        puts("");

    }

    return ;

}