一棵树n个节点，节点编号1至n，根节点是1号节点。

有n-1条边，第i条边连接结点u[i]和v[i]。

每个结点的价值一开始都是0。

有Q次操作，第i次操作的格式是： a[i]，b[i]，表示把以a[i]结点魏根的子树的所有结点的权值都增加b[i]。

当所有Q次结束以后，按照结点编号从小到大的次序，输出每个结点的权值。

输入格式

第一行，n和Q。2<=n<=200000, 1<=Q<=200000。

接下来有n-1行，第i行是u[i]和v[i]。1<=u[i]<v[i]<=n。

接下来有Q行，第i行是a[i]和b[i]。1<=a[i]<=n， 1<=b[i]<=10000。

输出格式

一行，共n个整数。

输入/输出例子1

输入：

4 3

1 2

2 3

2 4

2 10

1 100

3 1

输出：

100 110 111 110

输入/输出例子2

输入：

6 2

1 2

1 3

2 4

3 6

2 5

1 10

1 10

输出：

20 20 20 20 20 20

程序：

#include<bits/stdc++.h>
using namespace std;
int n,q,x,y;
long long d[410000],b[410000],yy;
vector<int>u[410000];
void dfs(int x,int fa)
{
	d[x]=b[x]+d[fa];
	for(int i=0;i<u[x].size();i++)
	{
		if(u[x][i]!=x)dfs(u[x][i],x);
	}
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		u[x].push_back(y);
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%d%lld",&x,&yy);
		b[x]+=yy;
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		printf("%lld ",d[i]);
	}
	return 0;
}