Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1385    Accepted Submission(s): 237

Problem Description

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.

 

Input

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⁵)

 

Output

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.

 

Sample Input

2

4 2

1 2

2 3

2 4

ADD1 1 4 1

ADD2 3 4 2

4 2

1 2

2 3

1 4

ADD1 1 4 5

ADD2 3 2 4

 

Sample Output

Case #1:

1 1 0 1

0 2 2

Case #2:

5 0 0 5

0 4 0
题意：给出一棵树，树上的点和边的权值开始都是0，有两种操作，对于第一种操作，ADD1：在u到v的路径上每个点的权值+w；对于第二种操作ADD2：在u到v的路径上每个边的权值+w；最后询问每个点的权值和每条边的权值（按照输入的顺序）
分析：首先两个dfs进行轻重链剖分，然后对于每个区间[L,R],在L的位置+w，在R+1的位置-w，保存在g1数组中，同理，对于边也一样，保存在g2数组里，最后从前往后做一遍扫描即可；
程序：

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

#include"stdio.h"

#include"string.h"

#include"iostream"

#include"map"

#include"string"

#include"queue"

#include"stdlib.h"

#include"algorithm"

#include"math.h"

#define M 110009

#define eps 1e-5

#define inf 100000000

#define mod 100000000

#define INF 0x3f3f3f3f

using namespace std;

struct node

{

    int v;

    node(int vv){v=vv;}

};

vector<node>edge[M];

int pos,son[M],fa[M],p[M],fp[M],deep[M],top[M],num[M],g1[M],g2[M],ans[M];

void dfs(int u,int f,int d)

{

    deep[u]=d;

    fa[u]=f;

    num[1]=1;

    for(int i=0;i<(int)edge[u].size();i++)

    {

        int v=edge[u][i].v;

        if(v==f)continue;

        dfs(v,u,d+1);

        num[u]+=num[v];

        if(son[u]==-1||num[son[u]]<son[v])

            son[u]=v;

    }

}

void getpos(int u,int sp)

{

    top[u]=sp;

    p[u]=pos++;

    fp[p[u]]=u;

    if(son[u]==-1)return;

    getpos(son[u],sp);

    for(int i=0;i<(int)edge[u].size();i++)

    {

        int v=edge[u][i].v;

        if(v==son[u]||v==fa[u])continue;

        getpos(v,v);

    }

}

void init()

{

    pos=0;

    memset(son,-1,sizeof(son));

    dfs(1,1,1);

    getpos(1,1);

}

void getnode(int u,int v,int d)

{

    int f1=top[u];

    int f2=top[v];

    while(f1!=f2)

    {

        if(deep[f1]<deep[f2])

        {

            swap(f1,f2);

            swap(u,v);

        }

        g1[p[f1]]+=d;

        g1[p[u]+1]-=d;

        u=fa[f1];

        f1=top[u];

    }

    if(u==v)

    {

        g1[p[u]]+=d;

        g1[p[u]+1]-=d;

        return;

    }

    if(deep[u]>deep[v])swap(u,v);

    g1[p[u]]+=d;

    g1[p[v]+1]-=d;

    return;

}

void getedge(int u,int v,int d)

{

    int f1=top[u];

    int f2=top[v];

    while(f1!=f2)

    {

        if(deep[f1]<deep[f2])

        {

            swap(f1,f2);

            swap(u,v);

        }

        g2[p[f1]]+=d;

        g2[p[u]+1]-=d;

        u=fa[f1];

        f1=top[u];

    }

    if(u==v)

        return;

    if(deep[u]>deep[v])swap(u,v);

    g2[p[son[u]]]+=d;

    g2[p[v]+1]-=d;

    return;

}

struct lede

{

    int u,v;

}e[M];

int main()

{

    int T,m,n,i,u,v,w,kk=1;

    char ch[22];

    cin>>T;

    while(T--)

    {

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

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

            edge[i].clear();

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

        {

            scanf("%d%d",&u,&v);

            edge[u].push_back(v);

            edge[v].push_back(u);

            e[i].u=u;

            e[i].v=v;

        }

        init();

        memset(g1,0,sizeof(g1));

        memset(g2,0,sizeof(g2));

        while(m--)

        {

            scanf("%s%d%d%d",ch,&u,&v,&w);

            if(strcmp(ch,"ADD1")==0)

                getnode(u,v,w);

            else

                getedge(u,v,w);

        }

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

        int sum=0;

        for(i=0;i<pos;i++)

        {

            sum+=g1[i];

            ans[i]=sum;

        }

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

        {

            if(i==1)

                printf("%d",ans[p[i]]);

            else

                printf(" %d",ans[p[i]]);

        }

        printf("\n");

        sum=0;

        for(i=1;i<pos;i++)

        {

            sum+=g2[i];

            ans[i]=sum;

        }

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

        {

            if(deep[e[i].u]<deep[e[i].v])

                swap(e[i].u,e[i].v);

            if(i==1)

                printf("%d",ans[p[e[i].u]]);

            else

                printf(" %d",ans[p[e[i].u]]);

        }

        printf("\n");

    }

}