#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<ll,ll>;
using tii = tuple<int,int,int>;
const int nmax = 1e6 + 5;
const int bmax = 20;
vector<int> g[nmax];
static inline int mjb(signed x) { return (x == 0? 0 : 32 - __builtin_clz(x)); }
static inline int ctz(signed x) { return (x == 0? -nmax : __builtin_ctz(x)); }
namespace Centroid {
int forbid[nmax];
int label[nmax];
void init(int node, int f) {
int once = 0, twice = 0;
for(auto x : g[node]) {
if(x == f) continue;
init(x, node);
twice |= once & forbid[x];
once |= forbid[x];
}
forbid[node] = (((1 << mjb(twice)) - 1) | once) + 1;
label[node] = ctz(forbid[node]);
}
int parent[nmax];
// ai ceva care tine date peste fii, si ceva ce tine date wrt parinte
void initparents(int n) {
int root;
auto dfs = [&](auto&& self, int node, int f) -> void {
if(node != root && (parent[node] == -1 || label[parent[node]] > label[root])) parent[node] = root;
for(auto x : g[node]) {
if(x == f || label[x] >= label[root]) continue;
self(self, x, node);
}
return;
};
for(int i = 1; i <= n; i++) parent[i] = -1;
for(root = 1; root <= n; root++) dfs(dfs, root, root);
for(int i = 1; i <= n; i++) if(parent[i] == -1) parent[i] = i;
}
}
namespace CentroidTree {
using namespace Centroid;
struct Batch {
int sum;
ll sumsq;
ll autoref() const { return ((ll)sum * sum - sumsq) / 2; }
void insert(int a) { sum += a; sumsq += abs(a) * a; }
};
ll multiref(const Batch& A, const Batch& B) {
return (ll)A.sum * B.sum;
}
struct Slider { // inserezi progresiv elemente tot mai mari.. nu?
vector<Batch> v;
int ptr[2] = {-1, -1};
void add(int p, int a) {
if(p >= sz(v))
v.resize(p + 1, Batch(0, 0));
v[p].insert(a);
}
void recalibrate() {
int before_modif = ptr[0];
bool qualified_before = (ptr[0] < sz(v) && v[ptr[0]].sum * v[ptr[0]].sum == v[ptr[0]].sumsq);
while(ptr[0] < sz(v) && v[ptr[0]].sum == 0) ptr[0]++;
if(ptr[0] < sz(v) && v[ptr[0]].sum * v[ptr[0]].sum == v[ptr[0]].sumsq) {
ptr[1] = ((ptr[0] != before_modif) || qualified_before? ptr[0] + 1 : ptr[1]);
while(ptr[1] < sz(v) && v[ptr[1]].sum == 0) ptr[1]++;
}
else ptr[1] = ptr[0];
}
void add(pii a) { add(a.first, a.second); }
void sub(pii a) { add(a.first, -a.second); }
pii getmultiref() {
if(ptr[1] == sz(v)) return pii{nmax, 0};
if(ptr[0] == ptr[1]) return pii{ptr[0] * 2, v[ptr[0]].autoref()};
return pii{ptr[0] + ptr[1], multiref(v[ptr[0]], v[ptr[1]])};
}
pii getref() {
if(ptr[0] == sz(v)) return pii{ptr[0], 0};
return pii{ptr[0], v[ptr[0]].sum};
}
};
Slider forparent[nmax]; // pentru parinte (gen, cadou ..); nu structura de date pentru parinte T_T
Slider overkids[nmax];
int distc[nmax][bmax];
Slider ANS;
void initsliders(int n) {
int root;
auto dfs = [&](auto&& self, int node, int f, int color, int d) -> void {
if(label[node] >= label[root]) return;
forparent[color].add(d, 1);
distc[node][label[root]] = d;
for(auto x : g[node]) {
if(x == f) continue;
self(self, x, node, color, d + 1);
}
return;
};
auto findson = [&](auto &&self, int node, int f) -> int {
if(label[node] == label[root] - 1) return node;
if(label[node] >= label[root]) return -1;
int mx = node;
auto updmx = [&](int a) { mx = (a == -1? mx : mx == -1? a : label[a] > label[mx]? a : mx); };
for(auto x : g[node]) {
if(x == f) continue;
updmx(self(self, x, node));
}
return mx;
};
for(root = 1; root <= n; root++) {
overkids[root].add(0, 1);
for(auto x : g[root]) {
int U = findson(findson, x, root);
if(U == -1) continue;
dfs(dfs, x, root, U, 1);
forparent[U].recalibrate();
//cerr << root << ": " << U << '\t' << forparent[U].getref().first << ' ' << forparent[U].getref().first << '\n';
overkids[root].add(forparent[U].getref());
}
overkids[root].recalibrate();
ANS.add(overkids[root].getmultiref());
}
ANS.recalibrate();
}
void eraseUpward(int p, int prev_p, int node) {
if(p == prev_p) return;
//cerr << p << ' ' << prev_p << " " << node << ": \t";
ANS.sub(overkids[p].getmultiref());
overkids[p].sub(forparent[prev_p].getref());
forparent[prev_p].sub(pii{distc[node][label[p]], 1});
forparent[prev_p].recalibrate();
//cerr << forparent[prev_p].getref().first << ' ' << forparent[prev_p].getref().second << '\t';
overkids[p].add(forparent[prev_p].getref());
overkids[p].recalibrate();
//cerr << overkids[p].getref().first << ' ' << overkids[p].getref().second << '\n';
ANS.add(overkids[p].getmultiref());
eraseUpward(parent[p], p, node);
}
void erase(int x) {
ANS.sub(overkids[x].getmultiref());
overkids[x].sub(pii{0, 1});
overkids[x].recalibrate();
//cerr << x << ": " << overkids[x].getref().first << ' ' << overkids[x].getref().second << '\n';
eraseUpward(parent[x], x, x);
ANS.add(overkids[x].getmultiref());
ANS.recalibrate();
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, type;
cin >> n >> type;
for(int i = 1, x, y; i < n; i++) {
cin >> x >> y;
g[x].emplace_back(y);
g[y].emplace_back(x);
}
Centroid::init(1, 1);
Centroid::initparents(n);
CentroidTree::initsliders(n);
//for(int i = 1; i <= n; i++) cerr << Centroid::label[i] << '\t' << Centroid::parent[i] << '\n';;
ll lastans = 0;
for(int i = 1; i <= n - 2; i++) {
ll x, pula;
cin >> x;
x ^= (lastans * type);
CentroidTree::erase(x);
tie(pula, lastans) = CentroidTree::ANS.getref();
cout << pula << ' ' << lastans << '\n';
}
}
/**
Istenem! Nu poate fi real.
-- Surse verificate
*/