提交记录

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 300010;

int n, Q;
int cnt, rt[N];
vector<int> gph[N];
int depth[N], siz[N];
struct Node
{
	int l, r, sum;
} tr[N * 40];

int merge(int p, int q, int l, int r)
{
	if (!p || !q) return p ? p : q;
	if (l == r)
	{
		tr[ ++ cnt].sum = tr[p].sum + tr[q].sum;
		return cnt;
	}
	int mid = l + r >> 1;
	int u = ++ cnt;
	tr[u].l = merge(tr[p].l, tr[q].l, l, mid);
	tr[u].r = merge(tr[p].r, tr[q].r, mid + 1, r);
	tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
	
	return u;
}

void update(int u, int l, int r, int x, int v)
{
	if (l == r) 
	{
		tr[u].sum += v;
		return;
	}
	int mid = l + r >> 1;
	if (x <= mid)
	{
		if (!tr[u].l) tr[u].l = ++ cnt;
		update(tr[u].l, l, mid, x, v);
	}
	else
	{
		if (!tr[u].r) tr[u].r = ++ cnt;
		update(tr[u].r, mid + 1, r, x, v);
	}
	tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}

int query(int u, int l, int r, int ql, int qr)
{
	if (!u) return 0;
	if (ql <= l && qr >= r) return tr[u].sum;
	int res = 0;
	int mid = l + r >> 1;
	if (ql <= mid && tr[u].l) res += query(tr[u].l, l, mid, ql, qr);
	else if (qr > mid && tr[u].r) res += query(tr[u].r, mid + 1, r, ql, qr);
	
	return res;
}

void dfs(int u, int fa)
{
	depth[u] = depth[fa] + 1;
	siz[u] = 1;
	for (int v : gph[u])
	{
		if (v == fa) continue;
		depth[v] = depth[u] + 1;
		dfs(v, u);
		siz[u] += siz[v];
	}
	
	rt[u] = ++ cnt;
	update(rt[u], 1, n, depth[u], siz[u] - 1);
	for (int v : gph[u])
	{
		if (v == fa) continue;
		rt[u] = merge(rt[u], rt[v], 1, n);
	}
}

signed main()
{
	cin >> n >> Q;
	for (int i = 1; i < n; i ++ )
	{
		int a, b;
		cin >> a >> b;
		gph[a].push_back(b);
		gph[b].push_back(a);
	}
	
	dfs(1, 0);
	
	for (int i = 1; i <= Q; i ++ )
	{
		int p, k;
		cin >> p >> k;
		int res = 0;
		res += min(k, depth[p] - 1) * (siz[p] - 1);
		res += query(rt[p], 1, n, depth[p] + 1, min(depth[p] + k, n));
		cout << res << '\n';
	}
	
	
	return 0;
}