Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.2 kB
4
Indexable
Never
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define se second
#define fi first
using namespace std;

int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

typedef tree <
    pair<int ,int>,
    null_type,
    less<pair<int ,int>>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;
*/

const int mod = 100000007;

const int N = 2e4+10;

vector<pair<ll, ll>>vec[N], ans;
vector<ll>id[N];

ll cost[N], n, k;
ll subtr[N], mp[N];

void clr()
{
    for(int i=0;i<=n;i++)
    {
        vec[i].clear();
        id[i].clear();
        subtr[i] = 0;
    }
}
void dfs1(int node, int par)
{
    subtr[node] = cost[node];

    for(auto it: id[node])
    {
        if(it==par)
        {
            continue;
        }
        dfs1(it, node);

        subtr[node] += subtr[it];
    }
}
void dfs(int node, int par)
{
    ans.pb({node, -cost[node]});

    for(auto it: vec[node])
    {
        if(it.se==par)
        {
            continue;
        }
        dfs(it.se, node);

        ans.pb({node, 0});
    }
    ans.pop_back();

    if(vec[node].size()==1 && node!=1) ans.pb({node, k-cost[node]});
    else ans.pb({node, k});
}
void solve(int tc)
{
    clr();

    cin>>n>>k;

    for(int i=0;i<n-1;i++)
    {
        int x, y;

        cin>>x>>y;

        id[x].pb(y);
        id[y].pb(x);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>cost[i];
    }

    dfs1(1, -1);

    for(int i=1;i<=n;i++)
    {
        for(auto it: id[i])
        {
            vec[i].pb({subtr[it], it});
        }
        sort(vec[i].rbegin(), vec[i].rend());
    }

    cout<<"Case "<<tc<<": "<<"YES"<<endl;

    ans.clear();

    dfs(1, -1);

    for(auto it: ans) cout<<it.fi<<' '<<it.se<<endl;
}
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	//pre();

	int tc = 1;
	cin>>tc;

	for(int test_case=1;test_case<=tc;test_case++)
    {
        solve(test_case);
    }
	return 0;
}
/*
1
5 20
1 2
2 3
3 4
4 5
20 40 20 10 10
*/